数据结构 实验二单链表的基本操作.docx

《数据结构 实验二单链表的基本操作.docx》由会员分享，可在线阅读，更多相关《数据结构 实验二单链表的基本操作.docx（9页珍藏版）》请在三一办公上搜索。

1、数据结构 实验二单链表的基本操作实验二：单链表的基本操作 一、 1、理解和掌握单链表的类型定义方法和结点生成方法。 2、掌握建立单链表和显示单链表元素的算法。 3、掌握单链表的查找、插入和删除算法 二、 1、建立一个整形数的单链表，手动输入10个数，并从屏幕显示单链表元素列表。 2、从键盘输入一个数，查找在以上创建的单链表中是否存在该数;如果存在，显示它的位置;如果不存在，给出相应提示。 3、删除上述单链表中指定位置的元素。 以下是程序部分代码，请调试并补充使之正确运行： LinList.h typedef struct Node DataType data; struct Node *nex

2、t; SLNode; void ListInitiate(SLNode *head) /*初始化*/ /*如果有内存空间，申请头结点空间并使头指针head指向头结点*/ if(*head = (SLNode *)malloc(sizeof(SLNode) = NULL) exit(1); (*head)-next = NULL; /*置链尾标记NULL */ int ListLength(SLNode *head) SLNode *p = head; /*p指向首元结点*/ int size = 0; /*size初始为0*/ while(p-next != NULL) /*循环计数*/ p

3、= p-next; size +; return size; int ListInsert(SLNode *head, int i, DataType x) /*在带头结点的单链表head的数据元素ai结点前*/ /*插入一个存放数据元素x的结点*/ SLNode *p, *q; int j; p = head; /*p指向首元结点*/ j = -1; /*j初始为-1*/ while(p-next != NULL & j next; j+; if(j != i - 1) printf(插入位置参数错！); return 0; /*生成新结点由指针q指示*/ if(q = (SLNode *)

4、malloc(sizeof(SLNode) = NULL) exit(1); q-data = x; q-next = p-next; /*给指针q-next赋值*/ p-next = q; /*给指针p-next重新赋值*/ return 1; int ListDelete(SLNode *head, int i, DataType *x) /*删除带头结点的单链表head的数据元素ai结点*/ /*删除结点的数据元素域值由x带回。删除成功时返回1；失败返回0*/ SLNode *p, *s; int j; p = head; /*p指向首元结点*/ j = -1; /*j初始为-1*/ w

5、hile(p-next != NULL & p-next-next!= NULL & j next; j+; if(j != i - 1) printf(插入位置参数错！); return 0; s = p-next; /*指针s指向数据元素ai结点*/ *x = s-data; /*把指针s所指结点的数据元素域值赋予x*/ p-next = s-next; /*把数据元素ai结点从单链表中删除指*/ free(s); /*释放指针s所指结点的内存空间*/ return 1; int ListGet(SLNode *head, int i, DataType *x) /*取数据元素ai和删除函

6、数类同，只是不删除数据元素ai结点*/ SLNode *p; int j; p = head; j = -1; while(p-next != NULL & j next; j+; if(j != i) printf(取元素位置参数错！); return 0; *x = p-data; return 1; void Destroy(SLNode *head) SLNode *p, *p1; p = *head; while(p != NULL) p1 = p; p = p-next; free(p1); *head = NULL; 2. main 程序 #include #include #i

7、nclude #include LinList.h void main(void) SLNode *head; int i , x; ListInitiate(&head); for(i = 0; i 10; i+) if(ListInsert(head, i, i+1) = 0) printf(错误! n); return; 三、 1.执行代码： #include #include #include #include LinList.h /*该文件包含pringtf等函数*/ /*该文件包含exit等函数*/ /*该文件包含malloc等函数*/ /*包含线性表文件*/ /*初始化*/ /*

8、插入10个数据元素*/ void main(void) SLNode *head; int i,x,t; ListInitiate(&head); printf(请输入10个数); for(i = 0; i next != NULL) /*循环计数*/ SLNode *p = head; int size = 0; /*p指向首元结点*/ /*size初始为0*/ /*如果有内存空间，申请头结点空间并使头指针head指向头结点*/ if(*head = (SLNode *)malloc(sizeof(SLNode) = NULL) exit(1); (*head)-next = NULL; /

9、*置链尾标记NULL */ /*初始化*/ p = p-next; size +; return size; int ListInsert(SLNode *head, int i, int x) /*在带头结点的单链表head的数据元素ai结点前*/ /*插入一个存放数据元素x的结点*/ if(j != i - 1) printf(插入位置参数错！); p = head; j = -1; /*p指向首元结点*/ /*j初始为-1*/ SLNode *p, *q; int j; while(p-next != NULL & j next; j+; return 0; /*生成新结点由指针q指示*

10、/ if(q = (SLNode *)malloc(sizeof(SLNode) = NULL) exit(1); q-data = x; q-next = p-next; p-next = q; return 1; /*给指针q-next赋值*/ /*给指针p-next重新赋值*/ int ListDelete(SLNode *head, int *x) /*删除带头结点的单链表head的数据元素ai结点*/ /*删除结点的数据元素域值由x带回。删除成功时返回1；失败返回0*/ p = head; j = -1; /*p指向首元结点*/ /*j初始为-1*/ SLNode *p, *s; i

11、nt j; while(p-next != NULL & p-next-next!= NULL & p-next-data !=*x) /*最终让指针p指向数据元素ai-1结点*/ p = p-next; j+; / if(j != i - 1) / / / / s = p-next; *x = s-data; /*指针s指向数据元素ai结点*/ /*把指针s所指结点的数据元素域值赋予printf(插入位置参数错！); return 0; x*/ int ListGet(SLNode *head, int i, int *x) /*取数据元素ai和删除函数类同，只是不删除数据元素ai结点*/

12、p = head; j = -1; SLNode *p; int j; p-next = s-next; free(s); return 1; /*把数据元素ai结点从单链表中删除指*/ /*释放指针s所指结点的内存空间*/ while(p-next != NULL & j next; j+; if(j != i) printf(取元素位置参数错！); return 0; *x = p-data; return 1; void Destroy(SLNode *head) p = *head; while(p != NULL) p1 = p; p = p-next; free(p1); SLNo

13、de *p, *p1; *head = NULL; void ListFind(SLNode *head, int t) void ListOutput(SLNode *p) do while(p-next != NULL&p-data!=t) if(p-next=NULL) else printf(数字 %d 存在的位置是：%d.n,t,s); printf(不存在该数字.n); p = p-next; s+; /*循环计数*/ SLNode *p = head; int s = 0; /*p指向首元结点*/ /*size初始为0*/ p = p-next; printf(%d ,p-data); while(p-next != NULL); 四、 五、