線性表的建立

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)線性表的建立、插入和刪除班級 ：計科021 姓名：羅晶晶 學(xué)號： 日期：2005/4/25實驗題目：1、建立一個順序存儲的線性表，實現(xiàn)線性表的插入、刪除操作2、建立一個單鏈表，實現(xiàn)單鏈表的插入、刪除操作運行環(huán)境 ：visual C+需求分析程序的功能：（1）建立一個按關(guān)鍵字有序的線性表，從鍵盤上輸入一個數(shù)，將該數(shù)插入到表中，使該線性表插入數(shù)據(jù)后仍按關(guān)鍵字有序。（2）建立一個線性表，從鍵盤上輸入一個數(shù)，查找表中是否存在該數(shù)，若有則刪除所有與該數(shù)相等的數(shù)。測試數(shù)據(jù)：順序存儲

2、的線性表：已建立一個有序的線性表為：請輸入要插入的數(shù)據(jù)：插入數(shù)據(jù)后的順序表為：請輸入要刪除的數(shù)據(jù)：刪除后的順序表為：單鏈表：請輸入記錄，輸入0則結(jié)束：1 2 0現(xiàn)在鏈表中的2個記錄是：1 2請輸入要插入的記錄：1現(xiàn)在鏈表中的3個記錄是：1 1 2 0請輸入要刪除的數(shù)據(jù)：1刪除了：1現(xiàn)在鏈表中的2個記錄是：1 2概要設(shè)計順序表的抽象數(shù)據(jù)類型的定義：ADT List 數(shù)據(jù)對象： D ai | ai ElemSet, i=1,2,.,n, n0 稱 n 為線性表的表長; 稱 n=0 時的線性表為空表。數(shù)據(jù)關(guān)系：R1 |ai-1 ,aiD, i=2,.,n 設(shè)線性表為 (a1，a2, . . . ，a

3、i，. . . ，an), 稱 i 為 ai 在線性表中的位序?；静僮鳎篒nitList( &L )操作結(jié)果：構(gòu)造一個空的線性表L。DestroyList( &L )初始條件：線性表 L 已存在。操作結(jié)果：銷毀線性表 L。ListEmpty( L )初始條件：線性表L已存在。操作結(jié)果：若L為空表，則返回TRUE，否則FALSE。ListLength( L )初始條件：線性表L已存在。操作結(jié)果：返回L中元素個數(shù)。GetElem( L, i, &e )初始條件：線性表L已存在，且 1iLengthList(L)。操作結(jié)果：用 e 返回L中第 i 個元素的值。LocateElem( L, e, c

4、ompare( ) )初始條件：線性表L已存在，e為給定值，compare( )是元素判定函數(shù)。操作結(jié)果：返回L中第1個與e滿足關(guān)系compare( )的元素的位序。若這樣的元素不存在，則返回值為0。ListTraverse(L, visit( )初始條件：線性表L已存在，Visit() 為某個訪問函數(shù)。操作結(jié)果：依次對L的每個元素調(diào)用函數(shù)visit( )。一旦visit( )失敗，則操作失敗。ListInsert( &L, i, e )初始條件：線性表L已存在，且 1iLengthList(L)+1 。操作結(jié)果：在L的第i個元素之前插入新的元素e，L的長度增1。ListDelete(&L,

5、i, &e)初始條件：線性表L已存在且非空，1iLengthList(L) 。操作結(jié)果：刪除L的第i個元素，并用e返回其值，L的長度減1。 ADT List詳細設(shè)計采用c語言定義相關(guān)的數(shù)據(jù)類型；#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct int *elem; int length; int listsize; SQLIST;其中部分操作的偽碼算法如下：void Create(SQLIST &L) /建立線性表L.elem =(int*)malloc(LIST_INIT_SIZE* sizeof(int);

6、if(!L.elem)printf(為線性表分配空間失敗!);L.length =0;L.listsize =LIST_INIT_SIZE;void Insert(SQLIST &A,int x) /實現(xiàn)有序的插入操作if(A.length =A.listsize) printf(線性表錯誤!);if(x A.elemA.length-1)A.elemA.length=x; elseint i=0;while(x = A.elemi) i+; for(int j=A.length; j=i; j-)A.elemj+1=A.elemj; A.elemi=x; A.length+; void li

7、stdelete(SQLIST &L,int x) /實現(xiàn)有序的刪除操作int i=0;if(L.length=0) coutERRORendl;while(i=L.length)if(L.elemi=x) for(int j=i+1;j=L.length-1;+j) L.elemj-1=L.elemj; L.length-;elsei+;3、#include#includetypedef struct student /單鏈表的存儲結(jié)構(gòu) long num;struct student* next;LINK;調(diào)試分析調(diào)試中遇到的問題及對問題的解決方法:在線性表中刪除一個元數(shù)時，要判斷是否有重復(fù)

8、的數(shù)據(jù)，有重復(fù)的話就要全部刪除，解決的方法是寫一個判斷的for語句。算法的時間復(fù)雜度和空間復(fù)雜度。在長度為n的順序表中插入一個元數(shù)的時間復(fù)雜度為0（n），刪除一個元數(shù)的時間復(fù)雜度為0（n）測試結(jié)果順序存儲的線性表單鏈表源程序（帶注釋）1、順序表的操作程序#include#include#include#include #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct int *elem; int length; int listsize; SQLIST;void Create(SQLIST &L) /建立線性表

9、L.elem =(int*)malloc(LIST_INIT_SIZE* sizeof(int);if(!L.elem)printf(為線性表分配空間失敗!);L.length =0;L.listsize =LIST_INIT_SIZE;void Insert(SQLIST &A,int x) /實現(xiàn)有序的插入操作if(A.length =A.listsize) printf(線性表錯誤!);if(x A.elemA.length-1)A.elemA.length=x; elseint i=0;while(x = A.elemi) i+; for(int j=A.length; j=i; j-

10、)A.elemj+1=A.elemj; A.elemi=x; A.length+; void listdelete(SQLIST &L,int x) /實現(xiàn)有序的刪除操作int i=0;if(L.length=0) coutERRORendl;while(i=L.length)if(L.elemi=x) for(int j=i+1;j=L.length-1;+j) L.elemj-1=L.elemj; L.length-;elsei+; coutnOKn刪除后的順序表為:nendl;void main()SQLIST s;Create(s); s.elem0=1; s.elem1=3;s.el

11、em2=3;s.elem3=4;s.elem4=9;s.length=5;printf(nn-順序表為-n);printf(nn已建立的順序表為:n);for(int i=0; is.length; i+) printf(%d ,s.elemi); printf(nn請輸入要插入的數(shù)據(jù):n);int tmp;scanf(%d,&tmp);Insert(s,tmp);printf(nn插入數(shù)據(jù)后的順序表為:n);for(i=0; ij; listdelete(s,j);for(int t=0; ts.length; t+)printf(%d ,s.elemt);getch(); 2、單鏈表表的操

12、作程序#include#includetypedef struct student /單鏈表的存儲結(jié)構(gòu)long num;struct student* next;LINK;int n; /定義一個全局變量(鏈表的結(jié)點個數(shù))LINK* Create() /建立LINK* head;LINK* p1,*p2;n=0;p1=p2=(LINK*)malloc(sizeof(LINK); scanf(%ld,&p1-num);head=NULL;while(p1-num !=0)n=n+1;if(n=1)head=p1;else /p1指向新開的結(jié)點,p2指向鏈表中的最后一個結(jié)點p2-next=p1;

13、/把p1所指的結(jié)點連在p2所指結(jié)點的后面p2=p1; /p2指向鏈表中的最后一個結(jié)點p1=(LINK*)malloc(sizeof(LINK);scanf(%ld,&p1-num);p2-next=NULL;return head;LINK* Insert(LINK *head,LINK *stud) /插入LINK *p0,*p1,*p2;p1=head; /p1指向第一個結(jié)點p0=stud; /p0指向待插入的結(jié)點if(head=NULL)head=p0; p0-next=NULL;elsewhile(p0-num = p1-num) & (p1-next !=NULL)p2=p1; /p

14、2指向p1剛才所指的結(jié)點p1=p1-next;if(p0-num num)if(head=p1) head=p0;elsep2-next=p0;p0-next=p1;elsep1-next=p0;p0-next=NULL;n=n+1;return head;LINK* Delete(LINK*head,long num) /刪除LINK *p1,*p2;if(head=NULL)printf(鏈表為空!nn);return(head);p1=head; / p1指向第一個結(jié)點while(num !=p1-num & p1-next !=NULL) /如果要刪除的不是第一個接點，p2=p1; /

15、將p1賦給p2，使p2指向剛才檢查過的結(jié)點p1=p1-next; /p1指向下一個結(jié)點if(num=p1-num) /如果刪除的是第一個結(jié)點if(p1=head)head=p1-next; /head指向原來的第2個結(jié)點elsep2-next=p1-next;printf(刪除了:%ld,num);n=n-1;elseprintf(沒有找到%ld,num);return(head);void print(LINK *head) /輸出LINK* p;printf(n現(xiàn)在鏈表中的%1d個記錄是:n,n);p=head;if(head !=NULL)doprintf(%ld n,p-num);p=p-next;while(p!=NULL);void main()printf(n-單鏈表的操作-nn);LINK *head,*stu;long Delete_num;printf(請輸入記錄,輸入0則結(jié)束:nn);head=Create(); /建立操作print(head);printf(請輸入要插入的記錄:n); /插入操作stu=(LINK*)malloc(sizeof(LINK);scanf(%1d,&stu-num);while(stu-num !=0)head=Inser