實驗二 鏈表的實現(xiàn)和應用

1、實驗二 鏈表的實現(xiàn)和應用一、 實驗目的掌握線性表的鏈式存儲結構設計與基本操作的實現(xiàn)二、 實驗內容與要求 定義線性表的鏈式存儲表示； 基于所設計的存儲結構實現(xiàn)線性表的基本操作； 編寫一個主程序對所實現(xiàn)的線性表進行測試； 線性表的應用：設線性表L1和L2分別代表集合A和B，試設計算法求A和B的并集C，并用線性表L3代表集合C；設線性表L1和L2中的數(shù)據(jù)元素為整數(shù)，且均已按值非遞減有序排列，試設計算法對L1和L2進行合并，用線性表L3保存合并結果，要求L3中的數(shù)據(jù)元素也按值非遞減有序排列。三、 數(shù)據(jù)結構設計 在主函數(shù)中實現(xiàn)函數(shù)的調用，從而實現(xiàn)線性表的插入、刪除、創(chuàng)建、顯示等。四、 測試結果 通過輸入

2、不同的數(shù)字（16）實現(xiàn)不同的操作，在兩個線性表結合時，線性表二在源程序中已給出的，通過操作可以得到非單調遞減的有序數(shù)列五、 心得體會 在寫程序的過程中要注意分析，參照其他標準程序，多上機運行一點點的改正錯誤，這樣才會有所提高。MAIN.C 方麗平 信計1203班 1130112321 最后修改時間2014/3/31#include<stdio.h>#include<stdlib.h>#define maxsize 1024typedef int datatype;typedef struct nodedatatype data;struct node * next;li

3、nkList;int main()linkList * CREATE();int INSERT(linkList *head, int value, int position);int DELETE(linkList *head, int position);int DISPLAY(linkList *head);linkList * COMBINE(linkList *head1, linkList *head2);linkList * head1;linkList * head2;linkList * head3;linkList * head;linkList * p1,* p2,* s

4、1,* s2,* r1,* r2;int position, value, i;head1 = malloc(sizeof(linkList);r1 = head1;head2 = malloc(sizeof(linkList);r2 = head2;for(i = 0; i< 20; i+)s1 = malloc(sizeof(linkList);s1 ->data = i;r1 ->next = s1;r1 = s1;s2 = malloc(sizeof(linkList);s2 ->data = i + 2;r2 ->next = s2;r2 = s2;r2

5、 -> next = NULL;r1 -> next = NULL;while(1) printf("the program n"); printf("can realize to create,insert,delete,display,etcn"); printf("1:create the ranked listn"); printf("2:insert a datan"); printf("3:delete a datan"); printf("4:display

6、all the datan"); printf("5:Combine two link lists of operationn"); printf("6:return,end of the programn"); printf("selection of operationn"); scanf("%d",&i); while ( i < 1 | i > 6 ) printf("please input againn"); scanf("%d",&

7、amp;i); switch(i) case 1: head = CREATE(); break; case 2: /*INSERT(p);*/ printf("Please input insert placen"); scanf("%d",&position);printf("Please input insert valuen"); scanf("%d",&value);INSERT(head, value, position); break; case 3: printf("Ple

8、ase input delete positionn"); scanf("%d",&value);DELETE(head, position); break; case 4: DISPLAY(head); break;case 5:printf("The list 1:n");DISPLAY(head1);printf("The list 2:n");DISPLAY(head2);printf("The combine list:n");head3 = COMBINE(head1, head2);

9、DISPLAY(head3);break; case 6: exit(0); break; linkList * CREATE() int value; linkList * head,* s,* r; head = malloc(sizeof(linkList); r = head; printf("input the data of the number,input 55 over!"); scanf("%d",&value); do s = malloc(sizeof(linkList); s ->data = value; r -&

10、gt;next = s; r = s; printf("input the data of the number"); scanf("%d",&value); while(value != 55); r -> next = NULL; return head;int INSERT(linkList *head,int value, int position)int j = 1;linkList *p,*s,*n;s = malloc(sizeof(linkList);s ->data = value;p = head;printf(&

11、quot;Note:if the position is greater than the length of the table will be put in the final");while(j < position)if( (p -> next) != NULL )p = p -> next;j +;n = p -> next;s -> next =n;p -> next = s;return 0; int DELETE(linkList *head, int position)int j;linkList *p;linkList *s;p

12、 = head;printf("Note:if the position is greater than the length of the table will be delete nothing!");for(j = 1;j < position; j +)if( (p -> next) != NULL )p = p -> next;elsereturn 0;s = p -> next;if(s -> next) != NULL)(*p).next = (*s).next;s = NULL;return 0;int DISPLAY(link

13、List *head)linkList *p;int i;i = 0;p = head -> next; while(p != NULL) printf("%5d",(*p).data); p = p -> next; i +; if(i % 5 = 0) printf("n"); return 0;linkList * COMBINE(linkList *head1, linkList *head2)linkList *head,*r;linkList *p1, *p2,*s;head = malloc(sizeof(linkList);r

14、 = head;p1 = malloc(sizeof(linkList);p2 = malloc(sizeof(linkList);p1 = head1 -> next;p2 = head2 -> next;dos = malloc(sizeof(linkList);if( (p1 != NULL) && (p2 != NULL) )if(p1 -> data < p2 -> data )s -> data = p1 -> data;p1 = p1 ->next;elses -> data = p2 -> data;p2 = p2 ->next;else if( (p1 != NULL) && (