数据结构上机实验报告(共23页).doc

精选优质文档-倾情为你奉上数据结构实验报告一顺序表要求：实现顺序表的初始化、在指定位置插入和删除元素。 算法思路：线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。顺序表的初始化操作就是为顺序表分配一个预定义大小的空间，并将线性表的当前长度设为“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<1|i>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<1|i>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); 程序运行：二 单链表要求：实现单链表的初始化、在指定位置插入和删除元素。算法思路：线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素。因此，为了表现每个元素与后继元素的逻辑关系需要用到指针。单链表的插入就是先生成一个数据域为插入元素的界点然后插入单链表中，并且修改前后节点的指针域，完成插入操作。反之删除链表元素时仅需修改前后两个元素的节点使之相连便可。程序代码：#define NULL 0#include "stdlib.h"#include"stdio.h"typedef struct LNode intdata; 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.在单链表插入元素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;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);程序运行：三 链表的合并要求：给定的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 Node long 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; 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 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; 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); printf("请输入链表数据："); p1 = create(a); printf("n你刚才输入的第一个链表信息:n "); print(p1); printf("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;程序运行：四 双向链表要求：实现双向链表的初始化、在指定位置插入和删除元素。 算法思路：因为单链表的节点中只有一个指示直接后继的指针域，因此只能从某节点出发顺指针往后寻查其它节点，若需寻查节点的直接前趋，则需从表头指针出发。所以在双向链表节点中有两个指针域，一个指向后继，一个指向前趋。程序代码：#include<stdio.h>#include<malloc.h>#define ERROR 0#define OK 1typedef int Elemtype; typedef struct myNode Elemtype 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"); 程序运行： 六队列要求：实现队列的插入和删除操作，以及循环队列的插入和删除操作。算法思路：队列是先进先出的线性表，只允许一端进行插入在另一端删除元素。所以链队列需要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 QNodeQElemType 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"); else printf("出队一个元素%dn",e); printf("出_队_列_序_列n"); while(!QueueEmpty(Q) DeQueue(Q,e); printf("%d ",e); printf("n"); 程序运行：七 串要求：实现常规的串的匹配，求解next函数和nextval函数，然后实现KMP算法。算法思路：子串的定位操作通常称做串的模式匹配，采用定长顺序存储结构，可以写出不依赖于其它串操作额匹配算法。KMP算法是在已知的next函数值的基础上执行的，我们可以从分析其定义出发用递推的方法求得next函数值，求得next函数值后便可执行KMP算法。程序代码：#include<stdio.h>#include <stdlib.h>#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.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+; else i=i-j+1; j=0; if (j>=t.len) k=i-t.len; else k=-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=-1|t.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; else v=-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; else nextvalj=nextvalk; else k=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+)