1、精選優質文檔-傾情為你奉上精選優質文檔-傾情為你奉上專心-專注-專業專心-專注-專業精選優質文檔-傾情為你奉上專心-專注-專業數據結構實驗報告一順序表要求：實現順序表的初始化、在指定位置插入和刪除元素。 算法思路：線性表的順序表示指的是用一組地址連續的存儲單元依次存儲線性表的數據元素。順序表的初始化操作就是為順序表分配一個預定義大小的空間，并將線性表的當前長度設為“0”。線性表的插入操作是在線性表的第i-1個數據元素和第i個元素之間插入新的數據元素，使得長度為n的線性表變成長度為n+1的線性表，而刪除恰好相反長度變為n-1的線性表，而且刪除點后面的元素要往前移動一個位。程序代碼：#includ

2、e #include #define MAXSIZE 50typedef char elemtype;typedef struct /類型定義 elemtype vMAXSIZE; int last; SeqList; SeqList *Init_SeqList() /初始化操作SeqList *L;L=(SeqList*)malloc(sizeof(SeqList);L-last=-1;return L;void Create(SeqList *L) /建立順序表 int i=0; elemtype ch; scanf(%c,&ch); while(ch!=n) L-vi+=ch; scan

3、f(%c,&ch); L-last=i-1; void PrintL(SeqList *L) /輸出順序表 int i; printf(此表為:n); for(i=0;ilast;i+) printf(%c,L-vi); printf(%cn,L-vi);void Length(SeqList *L) /順序表長度函數 printf(此表長度:n%d,L-last+1);printf(n);void insert(SeqList *L,int i,elemtype x) /插入函數 int j; if(L-last=0) printf(Error!n); if(iL-last) printf(

4、Error!); for(j=L-last;j=i-1;j-) L-vj+1=L-vj; L-vi-1=x; L-last+; PrintL(L); Length(L);void Delete(SeqList *L,int i) /刪除函數 int j; if(L-last=-1) printf(Error!); if(iL-last+1) printf(Error!); for(j=i;jlast;j+) L-vj-1=L-vj; L-last-; PrintL(L); Length(L);void main() /程序主函數 int i,j,k; elemtype a,b; SeqList

5、 *L; L=Init_SeqList(); printf(建立順序表：n);Create(L);PrintL(L); Length(L) ; printf(n); printf(請輸入你想插入的元素及其位置：n);scanf(%s %d,&b,&j);insert(L,j,b);printf(請輸入你想刪除的位置：n);scanf(%d,&k);Delete(L,k); 程序運行：單鏈表要求：實現單鏈表的初始化、在指定位置插入和刪除元素。算法思路：線性表的鏈式存儲結構的特點是用一組任意的存儲單元存儲線性表的數據元素。因此，為了表現每個元素與后繼元素的邏輯關系需要用到指針。單鏈表的插入就是先生

6、成一個數據域為插入元素的界點然后插入單鏈表中，并且修改前后節點的指針域，完成插入操作。反之刪除鏈表元素時僅需修改前后兩個元素的節點使之相連便可。程序代碼：#define NULL 0#include stdlib.h#includestdio.htypedef struct LNode intdata; struct LNode*next; LNode, *LinkList;void CreateList_L( LinkList *L);void ShowList(LinkList *L);LNode *GetElem(LinkList head);void InsertList(LinkLi

7、st *head);void DeleteList(LinkList head);void main() LNode *L; int j,loop=1; printf(n); while(loop)printf(1.建立單鏈表n); printf(2.在單鏈表插入元素n); printf(3.刪除單鏈表元素n); printf(請選擇序號(1-3): ); scanf(%d,&j); switch(j) case 1: CreateList_L(&L);break; case 2: InsertList(&L); break; case 3: DeleteList(L); break;prin

8、tf(結束此程序嗎？（0結束 1繼續）：n); scanf(%d,&loop);printf(n);void CreateList_L( LinkList *L) LNode *p;int flag=1;(*L)=(LinkList)malloc(sizeof(LNode);(*L)-next=NULL;printf(請輸入鏈表元素(輸 0 結束):n);while(flag)p=(LinkList)malloc(sizeof(LNode);p-next=NULL;scanf(%d,&p-data);if (p-data=0) break;p-next=(*L)-next;(*L)-next=

9、p; ShowList(L); void ShowList(LinkList *L)LinkList p;printf(頭節點- );for(p=(*L)-next;p!=NULL;p=p-next)printf(%d - ,p-data);printf(NULL !n);void InsertList(LinkList *head)LNode *pre,*s; int i,j,x;printf(請輸入插入位置:);scanf(%d,&i);printf(請輸入插入元素:);scanf(%d,&x); pre=*head;j=0;while (pre!=NULL & jnext; j+;s=(

10、LNode *)malloc(sizeof(LNode);s-data=x;s-next=pre-next;pre-next=s;ShowList(head);printf(n);void DeleteList(LinkList head)LNode *pre,*r; int i,j; pre=head;printf(請輸入刪除位置:);scanf(%d,&i);j=0;/*查找第i-1個結點*/while(pre-next!=NULL & jnext; j+; r=pre-next;pre-next=r-next ; free(r); ShowList(&head);程序運行：鏈表的合并要求

11、：給定的2個有序線性鏈表的合并（合并到1個新的鏈表中以及合并到其中的1個鏈表中兩種方式）。算法思路：先創建兩個有序線性鏈表a，b。然后將兩個有序線性鏈表a，b合并到a或者h中，得運用指針分別指向a，b當前待比較插入的節點，最后將兩個鏈表的元素有序歸并到表a或者h中。程序代碼：#include#include#include#include#define L sizeof(struct Node)struct Node long int number; struct Node *next;struct Node *create(int a) int n; struct Node *p1, *p2

12、, *head; head = NULL; n = 0; p2 = p1 = (struct Node *) malloc(L); scanf(%ld, &p1-number); while (a) n = n + 1; if (n = 1) head = p1; else p2-next = p1; p2 = p1; p1 = (struct Node *) malloc(L); if (a != 1) scanf(%ld, &p1-number); a-; p2-next = NULL; return (head);void print(struct Node *head) struct

13、Node *p; p = head; printf(數字:n); if (head != NULL) do printf(%ld, p-number); printf( ); p = p-next; while (p != NULL); printf(n);struct Node * inter_link(struct Node * chain1, int a, struct Node * chain2, int b) int temp; struct Node *head, *p1, *p2, *pos; if (a = b) head = p1 = chain1; p2 = chain2;

14、 else/*ba*/ head = p1 = chain2; p2 = chain1; temp = a, a = b, b = temp; pos = head; while (p2 != NULL) p1 = p1-next; pos-next = p2; pos = p2; p2 = p2-next; pos-next = p1; pos = p1; return head;void InsertSort(struct Node *p, int m) int i, j, t; struct Node *k; k = p; for (i = 0; i m - 1; i+) for (j

15、= 0; j number (p-next)-number) t = p-number; p-number = (p-next)-number; (p-next)-number = t; p = p-next; p = k; int main() struct Node *p1, *p2; int a; int b; int h; printf(請輸入第一個鏈表:n); printf(n輸入鏈表的長度a:n); scanf(%d, &a); printf(請輸入鏈表數據：); p1 = create(a); printf(n你剛才輸入的第一個鏈表信息:n ); print(p1); print

16、f(n 請輸入第二個鏈表:n); printf(n輸入鏈表的長度b:n); scanf(%d, &b); printf(請輸入鏈表數據：); p2 = create(b); printf(n你剛才輸入的第二個鏈表的信息:n); print(p2); p1 = inter_link(p1, a, p2, b); h = a + b; a = h; print(p1); InsertSort(p1, h); InsertSort(p1, a); printf(n排序后的鏈表a:n); print(p1); printf(n排序后的鏈表h:n); print(p1); return 0;程序運行：雙

17、向鏈表要求：實現雙向鏈表的初始化、在指定位置插入和刪除元素。 算法思路：因為單鏈表的節點中只有一個指示直接后繼的指針域，因此只能從某節點出發順指針往后尋查其它節點，若需尋查節點的直接前趨，則需從表頭指針出發。所以在雙向鏈表節點中有兩個指針域，一個指向后繼，一個指向前趨。程序代碼：#include#include#define ERROR 0#define OK 1typedef int Elemtype; typedef struct myNode Elemtype data;struct myNode *prior,*next;Node;Node * InitList()Node *H;H=

18、(Node *)malloc(sizeof(Node);if(!H)return ERROR;H-next =H-prior=H;return H;int AddFromEnd(Node *L,Elemtype e)Node *s,*r;int flag=1;Elemtype data;r=L;while(flag)printf(請輸入數據:);scanf(%d,&data);if(data=e)flag=0;elses=(Node *)malloc(sizeof(Node);if(!s)return ERROR;s-data=data;s-next=r-next;s-next-prior=s

19、;s-prior=r;r-next=s;r=s;return OK;int del(Node *L,int n,Elemtype *rec)Node *r;int c=0;if(n1)return ERROR;r=L;for(c=0;cnext != L;c+)r=r-next;if(r-next = L)return ERROR;r-next-prior=r-prior;r-prior-next=r-next;*rec=r-data;free(r);return OK;int insert(Node *L,int n,Elemtype num)Node *p,*s;int c;p=L-nex

20、t;if(n1)return ERROR;for(c=1;cnext;if(p=L)return ERROR;s=(Node *)malloc(sizeof(Node);if(!s)return ERROR;s-data=num;p-prior-next=s;s-prior=p-prior;s-next=p;p-prior=s;return OK;int ListLength(Node *L)Node *p;int c=0;p=L-next;while(p!=L)c+;p=p-next;return c;void Show(Node *L)Node *p;for(p=L-next;p!=L;p

21、=p-next)printf(%dn,p-data);int main()Node *La;Node *s;Elemtype rec;Elemtype num;Elemtype e=0;int n;La=InitList();printf(創建雙向鏈表:n); AddFromEnd(La,e);Show(La);printf(長度=%dn,ListLength(La);scanf(%d,&n);printf(請輸入插入元素序號及數值:n);scanf(%d%d,&n,&num);insert(La,n,num);Show(La);printf(長度=%dn,ListLength(La);pri

22、ntf(刪除什么元素?n);scanf(%d,&n);del(La,n,&rec);Show(La);printf(長度=%dn,ListLength(La);printf(%d 已刪除！n,rec);return 0;程序運行：棧 要求：實現順序棧的初始化、PUSH、POP等操作。算法思路:棧的順序存儲結構是利用一組地址連續的存儲單元依次存放自棧底到棧頂的數據元素，同時附設指針top指示棧頂元素在順序棧中的位置。所以先為棧分配一個基本存儲容量，當棧空間不足時在擴大。棧的初始化操作是按設定的初始分配量進行第一次存儲分配，base為棧頂指針始終指向棧底位置，若base為空表明棧結構不存在。Top

23、為棧頂指針，每次插入新的棧頂元素top增1，刪除棧頂元素，top減1.因此非空棧中棧頂指針始終在棧頂元素的下一位置上。程序代碼：#include#include #include#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define OK 1#define ERROR 0#define FALSE 0#define OVERFLOW 0#define TRUE 1typedef int Status;typedef int SElemType; typedef struct SElemType *base;SElemType *t

24、op;int stacksize; SqStack;Status InitStack(SqStack &S)S.base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)exit(OVERFLOW);S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK;Status Push(SqStack&S,SElemType e)、 if(S.top-S.base=S.stacksize) S.base = (SElemType *)realloc(S.base,

25、(S.stacksize + STACKINCREMENT)*sizeof(SElemType); if(!S.base) exit (OVERFLOW); S.top =S.base + S.stacksize; S.stacksize += STACKINCREMENT; *S.top+ = e;return OK;Status Pop(SqStack&S, SElemType&e)、 if(S.top=S.base) return ERROR; e = *-S.top; return OK;Status StackEmpty(SqStack&S) if(S.top=S.base) ret

26、urn TRUE; else return FALSE;main() SElemType e; SqStack S; printf(初始化棧n); InitStack(S); printf(棧為%sn,(StackEmpty(S)?空:非空); printf(請輸入棧元素1,2,3,4,5n); Push(S,1); Push(S,2); Push(S,3); Push(S,4); Push(S,5); printf(棧為%sn,(StackEmpty(S)?空:非空); printf(出棧序列); while(!StackEmpty(S) Pop(S,e); printf(%c,e) ; p

27、rintf(n); 程序運行： 六隊列要求：實現隊列的插入和刪除操作，以及循環隊列的插入和刪除操作。算法思路：隊列是先進先出的線性表，只允許一端進行插入在另一端刪除元素。所以鏈隊列需要2個分別指向隊頭和隊尾的指針。而空鏈隊列判決條件是頭指針和尾指針均指向頭結點。鏈隊列的插入和刪除只需修改尾指針或者頭指針就可以。程序代碼：#include#include#define NULL 0#define OK 1#define OVERFLOW 0#define ERROR 0typedef int Status;typedef int QElemType;typedef struct QNodeQEl

28、emType data;struct QNode *next; QNode, *QueuePtr;typedef struct QueuePtr front;QueuePtr rear;LinkQueue;Status InitQueue(LinkQueue&Q)Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(OVERFLOW);Q.front-next=NULL;return OK; Status EnQueue(LinkQueue&Q,QElemType e)QNode*p;p = (QueuePtr)m

29、alloc(sizeof(QNode);if(!p) exit(OVERFLOW);p-data = e; p-next = NULL;Q.rear-next = p;Q.rear = p;return OK; 、Status DeQueue(LinkQueue&Q,QElemType&e) QNode*p;if(Q.front=Q.rear) return ERROR;p = Q.front-next; e = p-data;Q.front-next = p-next;if(Q.rear=p) Q.rear = Q.front;free(p);return OK;、Status QueueE

30、mpty(LinkQueue&Q) if(Q.rear=Q.front) return 1;else return 0;void main() LinkQueue Q; QElemType e; printf(初_始_化_隊_列n); InitQueue(Q); printf(輸_入_隊_列_元_素1,3,5,7n); EnQueue(Q, 1); EnQueue(Q, 3); EnQueue(Q, 5); EnQueue(Q, 7); if(DeQueue(Q,e)=0) printf(隊空，不能出列n); else printf(出隊一個元素%dn,e); printf(出_隊_列_序_列

31、n); while(!QueueEmpty(Q) DeQueue(Q,e); printf(%d ,e); printf(n); 程序運行：串要求：實現常規的串的匹配，求解next函數和nextval函數，然后實現KMP算法。算法思路：子串的定位操作通常稱做串的模式匹配，采用定長順序存儲結構，可以寫出不依賴于其它串操作額匹配算法。KMP算法是在已知的next函數值的基礎上執行的，我們可以從分析其定義出發用遞推的方法求得next函數值，求得next函數值后便可執行KMP算法。程序代碼：#include#include #define maxsize 100 typedef struct char chmaxsize; int len; sqstring;void strassign(sqstring &str,char cstr) int i; for (i=0;cstri!=0;i+) str.chi=cstri; str.len=i;void dispstr(sqstring s) int i;if (s.len0) for (i=0;is.len;i+) printf (%c,s.chi); printf (n); int simple (sqstring s,sqstring t) int i=0,j=0,k; while (is.len&j=t.le