数据结构上机实验报告.docx

数据结构实验报告一.顺序表要求：实现顺序表的初始化、在指定位置插入和删除元素。算法思路：线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元 素。顺序表的初始化操作就是为顺序表分配一个预定义大小的空间，并将线性表的当前长度设 为“0”。线性表的插入操作是在线性表的第i-1个数据元素和第i个元素之间插入新的数据元 素，使得长度为n的线性表变成长度为n+1的线性表，而删除恰好相反长度变为n-1的线性表， 而且删除点后面的元素要往前移动一个位。程序代码：#include <stdio.h>#include <malloc.h>#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;scanf("%c”,&ch);L->last=i-1;void PrintL(SeqList *L)输出顺序表int i;printf（"此表为:n"）;for(i=0;i<L->last;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(i<1lli>L->last)printf("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(i<1lli>L->last+1)printf("Error!");for(j=i;j<=L->last;j+)L->vj-1=L->vj;L->last-;PrintL(L);Length(L);void main()程序主函数int i,j,k;elemtype a,b;SeqList *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);程序运行：' C: Lfsen5s-eliDes kto p II 色序表王 3_.ejce"建立顺序表至L23455&此表为:123455&此表长度：7M输入你想插入的元素及其位置:7此表为=L234575&此表长度：请1输云你想删除的位置：此表为:L234576此表长度：章按任意键继续_ _ _二单链表要求：实现单链表的初始化、在指定位置插入和删除元素。算法思路：线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素。 因此，为了表现每个元素与后继元素的逻辑关系需要用到指针。单链表的插入就是先生成一 个数据域为插入元素的界点然后插入单链表中，并且修改前后节点的指针域，完成插入操作。 反之删除链表元素时仅需修改前后两个元素的节点使之相连便可。程序代码：#define NULL 0#include "stdlib.h"#include"stdio.h”typedef struct LNodeint data;struct LNode *next; LNode, *LinkList;void CreateList_L( LinkList *L);void ShowList(LinkList *L);LNode *GetElem(LinkList head);void InsertList(LinkList *head);void DeleteList(LinkList head);void main()LNode *L;int j,loop=1;printf("n");while(loop)printf("1.建立单链表n");printf("2.在单链表插入元素/);printf("3.删除单链表元素/);printf("请选择序号(1-3):");scanf("%d”,&j);switch(j)case 1:CreateList_L(&L);break;case 2:InsertList(&L);break;case 3:DeleteList(L);break;printf("结束此程序吗？ (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=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 && j<i-1)pre=pre->next; j+;s=(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 && j<i-1) pre=pre->next; j+; r=pre->next;pre->next=r->next ;free(r);ShowList(&head);程序运行：建立.学链表.在箜链表插入兀素 匚叩柬皂链表元素 ,-选母序号<1-3>： 1 谱输元素【输a结束h3-±n点一44 -> 33 -> 22 -> 此程序吗？ (8结束在箪链表插入元素 叩怜堕链表元素擒入插入位置2 捶兀插；A元<；22 R点-> 44 -> 22NULL ?1 继续）：结束此崖序吗？ (3苗束1继续):建立单链表.在翠肆茬断' A空素链茬兀素选十圣序号(1-3)上逊幡位粉点一,44 -> 33 -> 22 -> W此程序吗？(3结束MULL i 继续）:三.链表的合并要求：给定的2个有序线性链表的合并(合并到1个新的链表中以及合并到其中的1个链表 中两种方式)。算法思路：先创建两个有序线性链表a，b。然后将两个有序线性链表a，b合并到a或者h 中，得运用指针分别指向a，b当前待比较插入的节点，最后将两个链表的元素有序归并到 表a或者h中。程序代码：#include<stdlib.h>#include<stdio.h>#include<conio.h>#include<malloc.h>#define L sizeof(struct Node)struct Nodelong int number;struct Node *next;；struct Node *create(int a)int n;struct Node *p1, *p2, *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;elsep2->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 Node *p;p = head;printf("数字:n");if (head != NULL)doprintf("%ld”, p->number);printf(" ");p = p->next; while (p != NULL);printf("n");struct Node * inter_link(struct Node * chainl, int a, struct Node * chain2, int b) ( int temp;struct Node *head, *p1, *p2, *pos;if (a >= b) (head = p1 = chain1;p2 = chain2; else/*b>a*/ (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 = 0; j < m - i - 1; j+) if (p->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);printfC请输入链表数据：”)；pl = create(a);printf(-n你刚才输入的第一个链表信息:n ");print(pl);printf("n请输入第二个链表:n");printf("n输入链表的长度b:n");scanf("%d”, &b);printfC请输入链表数据：")；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;程序运行：请输入第一个链君 输入链表的长度盐请输入链表数据；123134145蜚里输入的第一个槌表信息;123134145请输入第二个链表； 卜人链表的长度队 清输入链表数据！ iii 143 245部于； ill143数字：123ill245134143姓后的链费ill123134143屐后的链表把ill123134143请按任意键继续- 瞄地才输入的第二个措表的信息;145245145245145245四双向链表要求：实现双向链表的初始化、在指定位置插入和删除元素。算法思路：因为单链表的节点中只有一个指示直接后继的指针域，因此只能从某节点出发顺 指针往后寻查其它节点，若需寻查节点的直接前趋，则需从表头指针出发。所以在双向链表 节点中有两个指针域，一个指向后继，一个指向前趋。程序代码：#include<stdio.h>#include<malloc.h>#define ERROR 0#define OK 1typedef int Elemtype;typedef struct myNodeElemtype data;struct myNode *prior,*next;Node;Node * InitList()Node *H;H=(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;s->prior=r;r->next=s;r=s;return OK;int del(Node *L,int n,Elemtype *rec)Node *r;int c=0;if(n<1)return ERROR;r=L;for(c=0;c<n && r->next != 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->next;if(n<1)return ERROR;for(c=1;c<n && p!=L;c+)p=p->next;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=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);printf("删除什么元素?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为栈顶指针，每 次插入新的栈顶元素top增1，删除栈顶元素，top减1.因此非空栈中栈顶指针始终在栈顶 元素的下一位置上。程序代码：#include<stdio.h>#include <stdlib.h>#include<malloc.h>#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 *top;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,(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)return 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);printf("n");程序运行："C:User55 e liDes kto 栈.王概栈空列意 化空入非序仕 瑁害出请六. 队列要求：实现队列的插入和删除操作，以及循环队列的插入和删除操作。算法思路：队列是先进先出的线性表，只允许一端进行插入在另一端删除元素。所以链队列需 要2个分别指向队头和队尾的指针。而空链队列判决条件是头指针和尾指针均指向头结点。链 队列的插入和删除只需修改尾指针或者头指针就可以。程序代码：#include<stdio.h>#include<malloc.h>#define NULL 0#define OK 1#define OVERFLOW 0#define ERROR 0typedef int Status;typedef int QElemType;typedef struct QNode(QElemType 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)malloc(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 QueueEmpty(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");elseprintf("出队一个元素 %dn",e);printf("出 _队_列 _序_列 n");while(!QueueEmpty(Q)( DeQueue(Q,e);printf("%d ”,e);printf("n");程序运行：' CALfsersXs b liDes kto pliAU.±W-A-队列一元素135 J 个元素I出_队_列尊列2 5 7清按任意键继绿.七. 串要求：实现常规的串的匹配，求解next函数和nextval函数，然后实现KMP算法。算法思路：子串的定位操作通常称做串的模式匹配，采用定长顺序存储结构，可以写出不依 赖于其它串操作额匹配算法。KMP算法是在已知的next函数值的基础上执行的，我们可以 从分析其定义出发用递推的方法求得next函数值，求得next函数值后便可执行KMP算法。程序代码:#include<stdio.h>#include <stdlib.h>#define maxsize 100typedef 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.len>0)( for (i=0;i<s.len;i+)printf ("%c”,s.chi);printf ("n");int simple (sqstring s,sqstring t)int i=0,j=0,k;while (i<s.len&&j<t.len)if(s.chi=t.chj)i+;j+;elsei=i-j+1;j=0;if (j>=t.len)k=i-t.len;elsek=-1;return k;void getnext(sqstring t,int next ) int j ,k;j=0;k=-1;next0=-1;while (j<t.len-1) if (k=-1llt.chj=t.chk)j+;k+;nextj=k; else k=nextk;int kmpindex(sqstring s,sqstring t) int next maxsize,i=0,j=0,v;getnext(t,next);while (i<s.len&&j<t.len)if (j=-1|s.chi=t.chj) i+;j+;else j=nextj;if(j>=t.len)v=i-t.len;elsev=-1;return v;void getnextval(sqstring t,int nextval)int j=0,k=-1;nextval0=-1;while (j<t.len) if (k=-1|t.chj=t.chk) j+;k+;if (t.chj!=t.chk)nextvalj=k;elsenextvalj=nextvalk;elsek=nextvalk;int main ()int i,j;int next maxsize,nextval maxsize; sqstring s,t;strassign (s,"abcdeabcdefa");strassign (t,"bcdef");printf ("串 S:");dispstr(s);printf ("串 t:");dispstr(t);getnext (t,next);getnextval(t,nextval);printf (" i ");for (i=0;i<t.len;i+)printf ("%4d",i);printf("n");printf("ti ");for (i=0;i<t.len;i+)printf ("%4c”,t.chi);printf("n");printf("next ");for (i=0;i<t.len;i+)printf ("%4d”,nexti);printf("n");printf("nextval");for (i=0;i<t.len;i+)printf ("%4d”,nextvali);printf("n");printf ("kmp 算法：”)；j=kmpindex(s,t);if (j=-1) printf ("串匹配失败4”);else printf ("t 在 s 中的位置%dn",j);system("pause");程序运行：