数据结构上机实验线性表单链表源代码

实验一线性表的基本操作—单链表本课程实验中已知的预定义常量和类型如下：#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1/* #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行 */typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */typedef int Boolean;/* Boolean是布尔类型,其值是TRUE或FALSE */一、实验目的与基本要求1. 掌握数据结构中的一些基本概念。

2. 掌握单链表的定义、存储结构及其基本操作。

二、实验内容已知线性表的单链表存储结构为：/* 线性表的单链表存储结构 */struct LNode{ElemType data;struct LNode *next;};typedef struct LNode *LinkList;/* 另一种定义LinkList的方法 */编写函数void CreateList(LinkList *L，int n)动态生成一个单链表。

（L为单链表的头指针，它指向表中的第一个结点。

）Status ListInsert(LinkList L , int i , int e)实现在单链表L中第i个位置之前插入新的数据元素e。

若插入成功返回OK，否则返回ERROR。

void ListPrint（LinkList L）实现将单链表的元素依次输出到屏幕上。

void ListDelete(LinkList L，int i，int * e)在单链表L中删除第i个元素，并由e返回其值。

若删除成功返回OK（1），否则返回ERROR （0）。

void Merge（LinkList La，LinkList Lb，LinkList *Lc）完成已知两个按值非递减有序排列的单链表La和Lb，归并La和Lb得到一个新的单链表Lc，Lc的元素也按值非递减有序排列。

数据结构上机实验源代码栈的应用十进制数转换为八进制数，逆序输出所输入的数实验代码：//stack.h，头文件class stack{public:stack();bool empty()const;bool full()const;error_code gettop(elementtype &x)const;error_code push(const elementtype x);error_code pop();private:int count;elementtype data[maxlen];};stack::stack(){count=0;}bool stack::empty()const{return count==0;}bool stack::full()const{return count==maxlen;}error_code stack::gettop(elementtype &x)const{if(empty())return underflow;else{x=data[count-1];return success;}}error_code stack::push(const elementtype x){if(full())return overflow;data[count]=x;count++;return success;}error_code stack::pop(){if(empty())return underflow;count--;return success;}//主程序#include<iostream.h>enum error_code{overflow,underflow,success};typedef int elementtype;const int maxlen=20;#include"stack.h"void read_write() //逆序输出所输入的数{stack s;int i;int n,x;cout<<"please input num int n:";cin>>n;for(i=1;i<=n;i++){cout<<"please input a num:";cin>>x;s.push(x);}while(!s.empty()){s.gettop(x);cout<<x<<" ";s.pop();}cout<<endl;}void Dec_to_Ocx(int n) //十进制转换为八进制{stack s1;int mod,x;while(n!=0){mod=n%8;s1.push(mod);n=n/8;}cout<<"the ocx of the dec is:";while(!s1.empty()){s1.gettop(x);cout<<x;s1.pop();}cout<<endl;}void main(){int n;// read_write();cout<<"please input a dec:";cin>>n;Dec_to_Ocx(n);}队列的应用打印n行杨辉三角实验代码：//queue.hclass queue{public:queue(){count=0;front=rear=0;}bool empty(){return count==0;}bool full(){return count==maxlen-1;}error_code get_front(elementtype &x){if(empty())return underflow;x=data[(front+1)%maxlen];return success;}error_code append(const elementtype x){if(full())return overflow;rear=(rear+1)%maxlen;data[rear]=x;count++;return success;}error_code serve(){if(empty())return underflow;front=(front+1)%maxlen;count--;return success;}private:int count;int front;int rear;int data[maxlen];};//主程序#include<iostream.h>enum error_code{overflow,underflow,success};typedef int elementtype;const int maxlen=20;#include"queue.h"void out_number(int n) //打印前n行的杨辉三角{int s1,s2;int i;int j;int k;queue q;for(i=1;i<=(n-1)*2;i++)cout<<" ";cout<<"1 "<<endl;q.append(1);for(i=2;i<=n;i++){s1=0;for(k=1;k<=(n-i)*2;k++)cout<<" ";for(j=1;j<=i-1;j++){q.get_front(s2);q.serve();cout<<s1+s2<<" ";q.append(s1+s2);s1=s2;}cout<<"1 "<<endl;q.append(1);}}void main(){int n;cout<<"please input n:";cin>>n;out_number(n);}单链表实验实验目的:实验目的（1）理解线性表的链式存储结构。

数据结构线性表试验报告（最终定稿）第一篇：数据结构线性表试验报告线性表上机实习1、实验目的（1）熟悉将算法转换为程序代码的过程。

（2）了解顺序表的逻辑结构特性，熟练掌握顺序表存储结构的C 语言描述方法。

（3）熟练掌握顺序表的基本运算：查找、插入、删除等，掌握顺序表的随机存取特性。

（4）了解线性表的链式存储结构，熟练掌握线性表的链式存储结构的C语言描述方法。

（5）熟练掌握线性链表（单链表）的基本运算：查找、插入、删除等，能在实际应用中灵活选择适当的链表结构。

2、实验要求（1）熟悉顺序表的插入、删除和查找。

（2）熟悉单链表的插入、删除和查找。

3、实验内容: ① 顺序表（1）抽象数据类型定义typedef struct {TypeData data[maxsize];//容量为maxsize的静态顺手表int n;//顺序表中的实际元素个数}SeqList;//静态顺序表的定义在本次实验中，首先建立一个空的静态顺序表，然后键盘输入数据存入表中，然后进入菜单选择界面，通过不同的数字输入，实现对顺序表，删除，插入，查找，显示等操作。

（2）存储结构定义及算法思想在顺序表结构体的定义中，typedef int TypeData 为整型，存储结构如下：for(n=0;ncout<<“请输入线性表数据”<cin>>L.data[n];//顺序将数据存入顺序表}//其他存储与此类似，都是直接赋值与数组的某一位插入版块子函数：void insert(SeqList &L)//插入数据 {int a,b,c,k;cout<<“请输入插入的数及其插入的位置”<cin>>a>>b;if(b<=0||b>(L.n+1)){cout<<“不能在该位置插入”<k=L.data[b-1];L.data[b-1]=a;c=L.n;L.n=L.n+1;while(c>b){L.data[c]=L.data[c-1];c--;//通过循环，实现插入位置后的数据挨个往后移动一位}L.data[b]=k;} 顺序表的插入与删除操作类似，在插入与删除后，都要循环调整后面数组的每一位元素，同时记录数据元素的长度的标示符也要跟着改变。

数据结构实验5 配套代码1、#include <stdio.h>#include <stdlib.h>#include <ctype.h>#define OK 1#define ERROR 0#define OVERFLOW -2#define MAXSIZE 100#define NULL 0typedef int Status;typedef int ElemType;typedef struct LNode{ElemType data; //数据域struct LNode *next; //指针域}LNode,*LinkList; // *LinkList为Lnode类型的指针int main(){LNode *La=NULL;char choice1,choice2,choice3; // 菜单选项ElemType b[MAXSIZE],b1[MAXSIZE],x,z;int i,num,num1,n,m,e,y;Status InitList_L(LinkList &L);void CreateList_L(LinkList &L,ElemType a[],int n);Status DispList_L(LinkList L);int ListEmpty(LinkList L);Status GetElem_L(LinkList L,int i,ElemType &e);int LocateELem_L (LinkList L,ElemType e);Status ListInsert_L(LinkList &L,int i,ElemType e);Status ListDelete_L(LinkList &L,int i,ElemType &e);int ListLength_L(LinkList L);Status ClearList(LinkList & L);Status DestroyList_L(LinkList &L);InitList_L(La);printf("线性表中元素的个数?\n");scanf("%d",&num);printf("请输入元素:\n");for(i=0;i<num;i++)scanf("%d",&b[i]);CreateList_L(La,b,num);do{printf("\t单链表操作\n");printf("P-输出\t\tG-取值\n");printf("S-查找\t\tI-插入\n");printf("D-删除\t\tC-清空\n");printf("L-求表长\tQ-退出\n");scanf(" %c", &choice1);choice1 = toupper(choice1); //将字符choice转换为大写英文字母switch (choice1){case 'P':printf("线性表中的元素为:\n");DispList_L(La);break;case 'G':printf("要查找第几个元素?\n");scanf("%d",&n);m=GetElem_L(La,n,e);if(!m)printf("要查找的元素位置不合法!\n");elseprintf("要查找的第%d个元素是：%d\n",n,e);break;case 'S':printf("要查找的元素的值为：\n");scanf("%d",&x);m=LocateELem_L(La,x);if(!m)printf("线性表中不存在该元素!\n");elseprintf("%d是本表中的第%d个元素。

#include <stdio.h>#include <conio.h>#include <malloc.h>#include <stdlib.h>#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10#define OK 1#define ERROR -1#define OVERFLOW -1#define ENDFLAG 0typedef int Status;typedef int ElemType;#define OUTFORMAT "%d "#define INFORMAT "%d"typedef struct{ElemType *elem;int length;int listsize;}SqList;Status InitList(SqList *L){L->elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L->elem) ////// 如果没有分配成功exit(OVERFLOW); /////退出，显示（）内内容L->length=0;L->listsize=LIST_INIT_SIZE;return OK;}Status Inputdata(SqList *L){ ///////SqList *L定义首节点的地址ElemType temp,*newbase;printf("\nInput the data of the sequencial list:\nNote:0 is the ending flag:\n");scanf(INFORMAT,&temp);while(temp!=ENDFLAG){if(L->length>=L->listsize){newbase=(ElemType *)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType));////扩大空间，把旧的地址拷贝到新空间if(!newbase)exit(OVERFLOW);L->elem=newbase;L->listsize+=LISTINCREMENT;}L->elem[L->length++]=temp;scanf(INFORMAT,&temp);}return OK;}Status ListInsert(SqList *L,int i,ElemType e){ElemType *p,*q,*newbase;if(i<0||i>L->length)return ERROR;if(L->length>=L->listsize){Newbase =( elemType*)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase) exit(OVERFLOW);L->elem=newbase;L->listsize+=LISTINCREMENT;}q=&(L->elem[i-1]);for(p=&(L->elem[L->length-1]);p>=q;--p)*(p+1)=*p;*q=e;++L->length;return OK;}void MyDisplay(SqList L){int i;for(i=0;i<L.length;i++)printf(OUTFORMAT,L.elem[i]);printf("\n");}void main(void){SqList L;ElemType temp;int i;if(!InitList(&L)) { ////如果初始化失败printf("To initialize the sequencial list fail\n");getch(); //////如果失败，按任意键退出exit(0);}if(!Inputdata(&L)){printf("To input the data of the sequencial list fail\n");getch();exit(0);}MyDisplay(L);printf("Input the data that you want to insert:");scanf(INFORMAT,&temp);printf("Input the insert_location:");scanf("%d",&i);if(!ListInsert(&L,i,temp)){printf("To insert fail\n");getch();exit(0);}MyDisplay(L);getch();}。

数据结构实验线性表的链式表示和实现（源代码）件inc lude<stdio・h>#tnclude<malloc,h>#include<stdl)b.h>#define TURElttdefine FALSE 0ttdefine OK 1ttdefine ERROR 0ffdefine INEEASLIBE -1#define OVERFLOW -2 typedefint status; typ edefi ntelemty pe; struct nodeelemty pe date; struct node *next;struct node* createlistfnode *headjnt n)printf(“输入的n值不合法\汕); return head;node *p/q;head={struct node*)malloc(sizeof(struct node)); ifllhead) return head; head->next=NULL; head->date=n; q=head;inti=O;for(;i<n;)p=(struct no de*)malloc(sizeof(struct node));printf(“诸输入创建的结点数拯元索的scanf("%d'\&p・>datg);getcharO;p->next=NULL; q->next=p; q=P； i++；systemC^cIs"); return head;struct node* clearlistfnode *head)head=NULL; return head;status destroylist(node *head)head=NULL; free(head); return OK; statuslistempty(node *head)if|head==NULL)return OK;elsereturn ERROR;statusiist!ength(node *head)inti=0; node *p;p=head->next; while ⑴i++； if(p->next==NULL) break;p=p->next；prints该线性表的表长为%d\n\i);return OK;statusgetelem(node *headjnti,elemtype&e)node *p; p=head-> next; int n=1;printfC输入的i傅不合法\屮); return ERROR;while(n<i)p=p・> next;n++;iflp==NULL)printT输入的i值不合法W); return ERROR;e=p->date; return OK;statuslocatelemfnode *head,elemtvpe e)node *p; inti=l; p=head->next; while ⑴if(p->date==e&&p==NULL) break;p=p->next;i++；if)p==NULL)prints该线性表中没有％d这个数据元索\吧6);return ERROR;printfC-%d存在该线性表的第％d位\叭巳i）; return OK; statuspnorelem(node *headjntbelemtype&e)printfC该位上的数据元素为一个元索没有直接前驱元^\nj; return ERROR;struct node *p/q; p=head->next;int j=l;for(;p!=NULL;p=p->next)break;q=p;j++； iflp!=NULL)e*q・>date;printf（“该元索有数据元素并且直接前驱元索已传递给0\""）; returnOK;elseprintfC输入的i值不合法\门”); return ERROR;statusnextelem(node *head,inti,elenritype&e) struct node *p; p=head->next;int j=O;for(;p->next!=NULL; p=p->next)j++；break;iflp->next!=NULL)e=p・> next->date;printf（“该位上有后继元索且K接后继元索的垃已传递给e\n“）;return OK;if(p->next==：NULL&&(j+l)Ki)prints该位上的数据元素为最后一个元素没有直接后继元素Vn； returnERROR;else if(p==NULL&&{j+l)<i)printT输入的i值不合法W); return ERROR;struct node* insert(node *headjnti,elemtype e)printfC输入的i值不合法\门”); return head;struct node *q/p;q=head;int j=l;p=(struct no de*)malloc(sizeof(struct n ode)); p ・>date=e;while(j<i)if(q・>next==NULL) break;q=q->next; j++；p・> next=q->next; q・>next=p;elseprints输入的i值不合法\小;return head;struct node* delete_node{node *head,inti,elemtype&e)printf(”输入的i值不合法W); return head;struct node *p,*q; p 二head;int j=l; while(j<i)if(p・> next->next==NULL) break;p=p・> next;j++；q=p・>n ext;p ・>next=p・> next->next;e=q->date;free(q);ifijd)printfr输入的i值不合法\叶1;return head;status trip(node *head)struct node *p; p=head->next; inti=l;doprintf("第％d 位=~%d\n'\i,p*>datG); p=p・> next;i++；}vzhile(p!=NULL);return OK;main()struct node *head; char a,int n; elemty pe e; while(l)printfCl:构造一个线性後\"2:销毁线性表\n3:将已有线性表置为空表\"4：判断线性衣是否为空\n5:计算已有线性表中数据元素的个数\n”)；printfC'6:取出元索的值\n7:定位元索的位置\n8:插入新的数据元索\n9:删除某一个数据元索\冋显示该线性表中全部的元索W);printfC'b:取出特定位置的貞接前驱元素\皿:取出特定位置上直接后继元素00:退出\n\n\n'*);scanf("%c'\&a);getcharO;systemCcIs”)；switch(a)case O: exit(O);case T:printf("请输入需要创建元索的个数n\n"); scanf(” ％d”,&n);getcharO;head=createlist(head,n); break;case 2:if(destroylist{head)==OK)head=NULL;free(head);prints线性表销毁成功\");break;case 3:clearlist(head);printf(“线性表以置为空表\""); break;case '4':if(listempty(head)==OK) phntfC*线性表为空表\n“)； elsephntfC'线性表不为空表匕“)；break;case S:listlength(head);break;case '6':Printf(“请输入需要取出元素的位数冲“)；scanf(”％cr：&n);getcharO；P rintf("\n");getelem(head,n,e);printf("第％d位数据元索的值为%d\n'\n,e); break;case 7:p hntfC'W输入需要定位元素的值e=");scanfC'%d\&€);getcharO;P rintfCAn-);locatelem(head,e);break;case 8:printf(”请输入需要插入的位置n=");scanf(”％cr：&n);getcharO;printfCAn该位置上的数据元素的值曰)；scanf(-%cl\&e)； getcharO;p hntf("\n");head=insert(head, n^e);break;case 9:Printf(“诸输入需要删除的位置n=-); scanfr%cr&n); getcharO;delGte_node(head,n,G);printf(" C•删除第％(1位上的数据元素％d\n",n,e); break；case N:tnp(head);break;case V:phntfC'i#输入需要取出直接前驱元素的位数n=**)； scanfC'% cT&n);getcharO;if(p norelem(head,n,e)==OK)printf("\n第％€1位的直接前驱元素为%d\n'\n,e); break;case 'c';pmtf(“诸输入需要取出克接后继元素的位数冲“)； scanf("%d'\&n);getcharO；if(nextelem(head,n,e)==OK)printf("\n第％＜1位的直接后继元索为%d\n'\n,e); break；default:printf(”输入不合法 ... 请选择：\n'");printf("\n\n\n'');。

数据结构单链表实验代码1.有一个单链表的第一个节点指针为head，编写一个函数将该单链表逆置，即最后一个节点变成第一个节点，原来倒数第二个节点变成第二个节点，如此等等，在逆置中不能建立新的单链表。

#include#include#define bs -1typedef int db;typedef struct xiangjia{db data;struct xiangjia *next;}lb;lb *tou(){lb *L;L=(lb *)malloc(sizeof(lb));L->next=NULL;return L;}void get(lb *l){lb *L,*h;db x;L=l;printf("请输入你的数据,并在末尾输入-1以示结束\n\n");scanf("%d",&x);while(x!=bs){h=(lb *)malloc(sizeof(lb)); h->data=x;h->next=L->next;L->next=h;scanf("%d",&x);}}void put(lb *l){lb *L;L=l;printf("链表中的数据有:\n"); while(L->next!=NULL) {printf("%d",L->next->data); L=L->next;if(L->next!=NULL){printf("->");}}printf("\n");}main(){lb *a;a=tou();get(a);printf("逆序后的整数表:"); put(a);}2.编写程序，将若干整数从键盘输入，以单链表形式存储起来，然后计算单链表中结点的个数（其中指针P指向该链表的第一个结点）。