Question

实现C语言链表的按位置查找,按值查找和求链表的长度三个算法怎么编啊

Answer 1

#include <stdio.h>
#include <malloc.h>

typedef int DataType;

typedef struct node {
	DataType data;
	struct node *next;
}*LinkList,*pNode;

LinkList CreateList() {
	DataType data;
	LinkList head;
	pNode p;
	printf("输入整数(q to quit):");
	head = p = (pNode)malloc(sizeof(struct node)); // 生成头结点
	while(scanf("%d",&data) == 1) {
		p->next = (pNode)malloc(sizeof(struct node));
		p->next->data = data;
		p = p->next;
		printf("输入整数(q to quit):");
	}
	p->next = NULL;
	return head;
}

// 查找指定数据值
int FindData(LinkList head,DataType data) {
	pNode p = head->next;
	if(head == NULL || head->next == NULL) return 0;
	while(p) {
		if(p->data == data) return 1; // 找打时返回1
		p = p->next;
	}
	return 0; // 没找到返回0
}

// 查找指定位置的值(版本1)
int FindPosition1(LinkList head,int pos,DataType *data) {
	int i = 1;
	pNode p = head->next;
	if(head == NULL || head->next == NULL) return 0;
	while(p) {
		if(i == pos) {
			*data = p->data;
			return 1; // 找到时，返回1
		}
		p = p->next;
		++i;
	}
	return 0; // 没找到返回0；
}

// 返回链表的长度
int LengthList(LinkList head) {
	int cnt = 0;
	pNode p = head->next;
	if(head == NULL || head->next == NULL) return 0;
	while(p) {
		++cnt;
		p = p->next;
	}
	return cnt;
}

// 查找指定位置的值(版本2)
int FindPosition2(LinkList head,int pos,DataType *data) {
	int i = 1;
	pNode p = head->next;
	if(head == NULL || head->next == NULL) return 0;
	if(pos < 1 || pos > LengthList(head)) return 0;
	while(p) {
		if(i == pos) {
			*data = p->data;
			return 1; // 找到时，返回1
		}
		++i;
		p = p->next;
	}
	return 0; // 没找到返回0；
}

// 显示链表内容
void ShowList(LinkList head) {
	int cnt = 0;
	pNode p = head->next;
	while(p) {
		if(cnt && cnt % 10 == 0) printf("\n"); // 每行显示10个数据
		printf("%5d",p->data);
		p = p->next;
		++cnt;
	}
	if(cnt % 10) printf("\n");
}

void FreeMemory(LinkList head) {
	pNode q,p = head;
	while(p) {
		q = p;
		p = q->next;
		free(q);
	}
}

int main() {
	int pos;
	DataType x;
	printf("创建链表A。\n");
	LinkList A = CreateList();
	ShowList(A);
	printf("表A的长度是:%d\n",LengthList(A));
	printf("按位置查找，请输入位置:");
	fflush(stdin);
	scanf("%d",&pos);
	if(FindPosition2(A,pos,&x)) printf("位置%d的数据是%d\n",pos,x);
	else printf("%d:数据错误，查找失败。\n",pos);
	FreeMemory(A);
	return 0;
}