下载文档原格式
数据结构上机实验源代码栈的应用十进制数转换为八进制数，逆序输出所输入的数实验代码：//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）理解线性表的链式存储结构。
//头文件Head.h#include <stdlib.h>//exit#define OVERFLOW -2#define NULL 0#define TRUE 1#define ERROR 0#define OK 1#define INFEASIBLE -1typedef int Status;typedef int ElemType;typedef struct LNode //结点类型{ElemType data;struct LNode *prior;struct LNode *next;} LNode,*LinkList;Status comp(ElemType c1,ElemType c2) //判定函数(平方关系) {if(c1==c2*c2)return TRUE;elsereturn ERROR;}void visit(ElemType &c) //被调用的函数{printf("%d ",c);}Status InitList(LinkList &L){//初始化// LinkList L;L=(LinkList)malloc(sizeof(LNode));//生成结点L->next=NULL;return OK;}Status DestroyList(LinkList &L){//摧毁while(L->next){L=L->next;free(L);}return OK;}Status ClearList(LinkList &L){//清空L->next=NULL;return OK;}Status ListEmpty(LinkList L){//判空if(L->next==NULL)return TRUE;return ERROR;}Status ListLength(LinkList &L){//长度LinkList p;p=L->next;int j=0;while(p){j++;p=p->next;}return j;}Status GetElem(LinkList L,int i,ElemType e){//取值LinkList p;p=L->next;int j=1;while(p&&j<i){p=p->next;j++;}if(!p||j>i)return ERROR;return OK;}int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType)) {//返回L中第1个与e满足关系compare()的数据元素的位序LinkList p;int i=0;//while(i<=ListLength(L)&&!compare(p->data,e))while(p&&!compare(p->data,e)){p=p->next;i++;}if(p)//////return i;return ERROR;}Status PriorElem(LinkList L,ElemType cur_e,ElemType &pre_e) {//返回前驱LinkList p;int i=2;p=L->next;while(p&&p->data!=cur_e){i++;p=p->next;}if(!p)return INFEASIBLE;else{pre_e=p->prior->data;return pre_e;}}Status NextElem(LinkList L,ElemType cur_e,ElemType &next_e) {//返回后继LinkList p;p=L;int i=1;while(p->next&&p->data!=cur_e){i++;p=p->next;}if(p==NULL)return INFEASIBLE;else{next_e=p->next->data;return next_e;}}Status ListInsert(LinkList &L,ElemType i,ElemType e){//插入LinkList p,s;p=L;int j=0;while(p&&j<i-1){p=p->next;++j;}if(!p||j>i-1)return ERROR;s=(LinkList)malloc(sizeof(LNode));//生成新的结点s->data=e;s->next=p->next;p->next=s;return OK;}Status ListDelete(LinkList &L,ElemType i,ElemType &e){//删除LinkList p;p=L;int j=0;while(p&&j<i-1){p=p->next;++j;}if(!(p->next)||j>i-1)return ERROR;e=p->next->data;p->next=p->next->next;return OK;}Status ListTraverse(LinkList L){ //依次对L的每个数据元素调用函数vi()。
#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();}。
浙江大学城市学院实验报告课程名称数据结构基础实验项目名称实验五线性表的链式表示和实现学生姓名专业班级学号实验成绩指导老师（签名）日期一.实验目的和要求1、了解线性表的链式存储结构，学会定义线性表的链式存储结构。
2、掌握单链表、循环单链表的一些基本操作实现函数。
二.实验内容1、设线性表采用带表头附加结点的单链表存储结构，请编写线性表抽象数据类型各基本操作的实现函数，并存放在头文件LinkList.h中（注：教材上为不带表头附加结点）。
同时建立一个验证操作实现的主函数文件test5.cpp，编译并调试程序，直到正确运行。
提示：⑴单向链表的存储结构可定义如下：struct LNode { // 定义单链表节点类型ElemType data; // 存放结点中的数据信息LNode *next; // 指示下一个结点地址的指针}⑵线性表基本操作可包括如下一些：①void InitList (LNode *&H) //初始化单链表②void ClearList(LNode *&H) //清除单链表③int LengthList (LNode *H) //求单链表长度④bool EmptyList (LNode *H) //判断单链表是否为空表⑤ElemType GetList (LNode *H, int pos)//取单链表第pos 位置上的元素⑥void TraverseList(LNode *H) //遍历单链表⑦bool InsertList ( LNode *&H, ElemType item, int pos)//向单链表插入一个元素⑧bool DeleteList ( LNode *&H, ElemType &item, int pos)//从单链表中删除一个元素⑶带表头附加结点的单链表初始化操作的实现可参考如下：void InitList(LNode *&H){ //构造一个空的线性链表H，即为链表设置一个头结点，//头结点的data数据域不赋任何值，头结点的指针域next则为空H=(LNode *)malloc(sizeof(LNode)); // 产生头结点Hif (!H) exit(0); // 存储分配失败，退出系统H->next=NULL; // 指针域为空}2、选做部分：编写一个函数void MergeList(LNode *&La, LNode *&Lb, LNode *&Lc)，实现将两个有序单链表La和Lb合并成一个新的有序单链表Lc，同时销毁原有单链表La和Lb。
#include <stdio.h>#include <stdlib.h>#include <iostream.h>#define ListSize 100typedef int DataType;typedef struct node{ DataType data;struct node *next;}ListNode;typedef ListNode *LinkList;void main(){LinkList L,L1,L2,L3;ListNode *p;char ch;int position;DataType newelem,min,max;LinkList InitList();void PrintList(LinkList L);LinkList CreateListF();LinkList CreateListR();int LengthList(LinkList L);void InsertList(LinkList L,DataType newelem,int position);void DeleteList(LinkList L,int position);LinkList LocateList(LinkList L,DataType newelem);void DestroyList(LinkList L);void ReverseList1(LinkList L);void ReverseList2(LinkList L);LinkList MerageList(LinkList L1,LinkList L2);void Delx(LinkList L,DataType newelem);void SplitList(LinkList L,LinkList L1,LinkList L2);void Delmintomax1(LinkList L,int min,int max);void Delmintomax2(LinkList L,int min,int max);void Delrepeat(LinkList L);void Sortlist(LinkList L);void Delminnode(LinkList L);void Joseph();void Invert();do {cout<<endl;cout<<" *******************链式线性表功能菜单************************"<<endl;cout<<" * a：初始化单链表b：建立单链表(头插法)*"<<endl;cout<<" * c: 建立单链表(尾插法) d：求单链表长度*"<<endl;cout<<" * e：单链表插入元素f：单链表删除元素*"<<endl;cout<<" * g：无序单链表查找元素h：释放单链表*"<<endl;cout<<" * i：逆置单链表(头插入) j: 逆置单链表*"<<endl;cout<<" * k：二个递增单链表合并成递减l: 删除值为X的结点*"<<endl;cout<<" * m：将单链表拆分成两个单链表n: 递增单链表删除某数值区间*"<<endl;cout<<" * o：无序单链表删除某数值区间p: 递增单链表删除重复*"<<endl;cout<<" * q：单链表直接插入排序r: 单链表删除最小值*"<<endl;cout<<" * s：约瑟夫问题t: 循环单链表逆置*"<<endl;cout<<" * u：v: *"<<endl;cout<<" * w：x: *"<<endl;cout<<" * y: z：退出*"<<endl;cout<<"*************************************************************"<<endl;cout<<" 请输入你的选择：";cin>>ch;switch (ch){case 'a':L=InitList();PrintList(L);break;case 'b':L=CreateListF();PrintList(L);break;case 'c':L=CreateListR();PrintList(L);break;case 'd':PrintList(L);cout<<" 单链表长度为："<<LengthList(L)<<endl;break;case 'e':cout<<" 请输入插入位置：";cin>>position;cout<<" 请输入插入元素：";cin>>newelem;InsertList(L,newelem,position);PrintList(L);break;case 'f':cout<<" 请输入删除第几个元素：";cin>>position;DeleteList(L,position);PrintList(L);break;case 'g':cout<<" 请输入查找元素：";cin>>newelem;p=LocateList(L,newelem);if (p!=NULL)cout<<p->data<<endl;PrintList(L);break;case 'h':PrintList(L);DestroyList(L);break;case 'i':PrintList(L);ReverseList1(L);PrintList(L);break;case 'j':PrintList(L);ReverseList2(L);PrintList(L);break;case 'k':cout<<" 创建第一个递增有序单链表：";L1=CreateListR();PrintList(L1);cout<<" 创建第二个递增有序单链表：";L2=CreateListR();PrintList(L2);L3=MerageList(L1,L2);cout<<" 递减有序单链表为：";PrintList(L3);break;case 'l':cout<<" 请输入要删除的数据元素：";cin>>newelem;PrintList(L);Delx(L,newelem);PrintList(L);break;case 'm'://利用原空间拆分L=CreateListR();PrintList(L);L1=new(ListNode);L1->next=NULL;L2=new(ListNode);L2->next=NULL;SplitList(L,L1,L2);PrintList(L1);PrintList(L2);break;case 'n':cout<< " 请输入要删除元素的数值区间min,max：";cin>>min;cin>>max;PrintList(L);Delmintomax1(L,min,max);PrintList(L);break;case 'o':cout<< " 请输入要删除元素的数值区间min,max：";cin>>min;cin>>max;PrintList(L);Delmintomax2(L,min,max);PrintList(L);break;case 'p':PrintList(L);Delrepeat(L);PrintList(L);break;case 'q':PrintList(L);Sortlist(L);PrintList(L);break;case 'r':PrintList(L);Delminnode(L);PrintList(L);break;case 's':Joseph();break;case 't':Invert();break;case 'u':break;case 'v':break;case 'w':break;case 'x':break;case 'y':break;default:break;}}while (ch!='z');}LinkList InitList(){ListNode *head;head=new(ListNode);head->next=NULL;return head;}void PrintList(LinkList L) {ListNode *p;if (L)p=L->next;elsep=NULL;cout<<endl;while (p!=NULL){cout<<" "<<p->data;p=p->next;}}LinkList CreateListF(){ListNode *head,*q;int count,i;head=new(ListNode);head->next=NULL;cout<<" 请输入元素个数：";cin>>count;for (i=1;i<=count;i++){q=new(ListNode);cin>>q->data;q->next=head->next;head->next=q;}return head;}LinkList CreateListR(){ListNode *head,*p,*q;int count,i;head=new(ListNode);p=head;cout<<" 请输入元素个数：";cin>>count;for (i=1;i<=count;i++){q=new(ListNode);cin>>q->data;p->next=q;p=q;}p->next=NULL;return head;}int LengthList(LinkList L){int i;ListNode *p;p=L;i=-1;while (p){i++;p=p->next;}return i;}void InsertList(LinkList L,DataType newelem,int position) {int i;ListNode *p,*s;i=position;p=L;while ((p->next!=NULL) && (i>1)){i--;p=p->next;}s=new(ListNode);s->data=newelem;s->next=p->next;p->next=s;}void DeleteList(LinkList L,int position){ListNode *p,*s;int i;p=L;i=position;while ((i>1) && (p!=NULL)){i--;p=p->next;}if (p!=NULL){s=p->next;if (s!=NULL){p->next=s->next;free(s);}}}LinkList LocateList(LinkList L,DataType newelem) {ListNode *p;p=L->next;while ((p!=NULL) && (p->data!=newelem)) p=p->next;return p;}void DestroyList(LinkList L){ListNode *p;while (L->next){p=L->next;L->next=p->next;free(p);}free(L);L=NULL;}void ReverseList1(LinkList L){ListNode *p,*q;p=L->next;L->next=NULL;while (p!=NULL){q=p->next;p->next=L->next;L->next=p;p=q;}}void ReverseList2(LinkList L){ListNode *p,*q,*r;p=L->next;q=p->next;p->next=NULL;while (q){r=q->next;q->next=p;p=q;q=r;}L->next=p;}LinkList MerageList(LinkList L1,LinkList L2) {ListNode *head,*p1,*p2,*s;head=new(ListNode);head->next=NULL;p1=L1->next;p2=L2->next;while (p1 && p2){s=new(ListNode);if (p1->data<p2->data){s->data=p1->data;p1=p1->next;}else{s->data=p2->data;p2=p2->next;}s->next=head->next;head->next=s;}if (p1)while (p1){s=new(ListNode);s->data=p1->data;s->next=head->next;head->next=s;p1=p1->next;}elsewhile (p2){s=new(ListNode);s->data=p2->data;s->next=head->next;head->next=s;p2=p2->next;}return head;}void Delx(LinkList L,DataType newelem){ListNode *p,*s;p=L;while ((p->next) && (p->next->data!=newelem))p=p->next;if (p->next){s=p->next;p->next=s->next;free(s);}}void SplitList(LinkList L,LinkList L1,LinkList L2) //L1放单数，L2放双数{ListNode *p,*p1,*p2;p1=L1;p2=L2;while (L->next){p=L->next;if (p->data%2==1){p1->next=p;p1=p;}else{p2->next=p;p2=p;}}p1->next=NULL;p2->next=NULL;}void Delmintomax1(LinkList L,int min,int max){ListNode *p,*q,*r;p=L;while (p->next && p->next->data<min)p=p->next;q=p->next;while (q && q->data<=max){r=q->next;free(q);q=r;}p->next=q;}void Delmintomax2(LinkList L,int min,int max){ListNode *p,*q;p=L;while (p->next)if (p->next->data>=min && p->next->data<=max){q=p->next;p->next=q->next;free(q);}else}void Delrepeat(LinkList L){ListNode *p,*q;p=L->next;q=p->next;while (q){if (p->data==q->data){p->next=q->next;free(q);}elsep=q;q=p->next;}}void Sortlist(LinkList L){ListNode *p,*q,*r;p=L;q=p->next;p->next=NULL;while (q){p=L;while (p->next && p->next->data<q->data)p=p->next;r=q->next;q->next=p->next;p->next=q;q=r;}}void Delminnode(LinkList L){ListNode *p,*pre,*minp,*minpre;pre=L;p=pre->next;minpre=pre;minp=p;while (p){if (p->data<minp->data){minpre=pre;minp=p;}pre=p;p=p->next;}minpre->next=minp->next;free(minp);}void Joseph(){ListNode *p,*q,*s;int i;p=new(ListNode);p->data=1;q=p;for (i=2;i<=30;i++){s=new(ListNode);s->data=i;q->next=s;q=s;}q->next=p;while (q->next!=q){for (i=1;i<=9;i++)q=q->next;p=q->next;cout<<p->data<<" ";q->next=p->next;free(p);}cout<<q->data;free(q);}void Invert(){ListNode *p,*q,*s;int i;p=new(ListNode);p->data=1;q=p;for (i=2;i<=10;i++){s=new(ListNode);s->data=i;q->next=s;q=s;}q->next=p;while (p!=q){cout<<" "<<p->data;p=p->next;}cout<<" "<<p->data<<endl;p=q->next;q->next=q;while (p!=q){s=p->next;p->next=q->next;q->next=p;p=s;}cout<<" "<<q->data;p=q->next;while (p!=q){cout<<" "<<p->data;p=p->next;}}。
线性表（单链表、循环链表-python实现）⼀、线性表 线性表的定义： 线性表是具有相同数据类型的有限数据的序列。
线性表的特点： 出了第⼀个元素外，每个元素有且仅有⼀个直接前驱，除最后⼀个元素外有且只有⼀个后继。
线性表是⼀种逻辑结构，表⽰元素之间的⼀⼀的相邻关系，顺序表和链表是指存储结构，两者属于不同的概念。
线性表的顺序表⽰： 线性表的顺序存储即数组的动态、静态分配，特点是可以随机访问。
线性表的链式表⽰： 线性表的链式存储即单链表、双连表、循环单链表以及循环双连表，特点是随机插⼊，不可随机访问。
单链表的实现（python）：#定义每个节点class Node:def__init__(self,data):self.data=dataself.next=Noneclass linkList:#初始化头结点def__init__(self,n):self.head=Node(None)self.n=n#头插法建⽴链表def listCreateForward(self):if self.n==0:return Falseelse:temp=self.headfor i in range(1,self.n+1):print('请输⼊第{0}个节点:'.format(i))num = input()node = Node(num)node.next=temp.nexttemp.next = node#尾插法建⽴链表def listCreateBackward(self):if self.n==0:return Falseelse:temp=self.headfor i in range(1,self.n+1):print('请输⼊第{0}个节点:'.format(i))num = input()node = Node(num)temp.next=nodetemp=node#读取链表def readList(self):if self.n==0:print("空链表！")else:temp = self.headwhile temp.next!=None:temp = temp.nextprint(temp.data,end='')#链表长度def Length(self):i=0temp=self.headwhile temp.next!=None:temp=temp.nexti+=1return i#按值查找def locateElem(self,num):i = 0temp = self.headwhile temp.next != None:temp = temp.nexti += 1if int(temp.data)==num:return ireturn None#按位置查找def getElem(self,j):i = 0temp = self.headwhile temp.next != None:temp = temp.nexti += 1if int(j)==i:return temp.datareturn None#按位置插⼊数字def listInsert(self,j,num):if int(j)<0:return Noneelif self.Length()<j:return Noneelse:i = 0temp = self.headwhile temp.next != None:i += 1if int(j) == i:node=Node(num)node.next=temp.nexttemp.next=nodetemp = temp.next#删除特定元素def deleteData(self,num):temp=self.headwhile True:if temp.next==None:break#当这个节点是尾节点时if int(temp.next.data)==num and temp.next.next==None: temp.next=Nonebreakelif int(temp.next.data)==num:temp.next=temp.next.nexttemp=temp.next#删除特定位置的元素def deleteElem(self,j):if j==1:self.head.next=self.head.next.nextelif j==self.Length() :temp=self.head.nextwhile True:if temp.next.next==None:temp.next=Nonebreaktemp=temp.nextelif j<self.Length():i=2temp=self.head.nextwhile True:if i==j:temp.next=temp.next.nextelse:print('erro')return Nonelinklist1=linkList(5)linklist1.listCreateBackward()linklist1.readList()length=linklist1.Length()print('length={0}'.format(length))locate=linklist1.locateElem(5)print('5在位置{0}'.format(locate))data=linklist1.getElem(3)print('第3个位置是{0}'.format(data))linklist1.listInsert(1,111)linklist1.readList()print('\n删除111(第⼀个元素):')linklist1.deleteData(111)linklist1.readList()print('\n删除5(末尾的元素)')linklist1.deleteData(5)linklist1.readList()print('\n删除第⼀个元素:')linklist1.deleteElem(1)linklist1.readList()print('\n删除末尾的元素')linklist1.deleteElem(3)linklist1.readList()结果：请输⼊第1个节点:1请输⼊第2个节点:2请输⼊第3个节点:3请输⼊第4个节点:4请输⼊第5个节点:51 2 3 4 5 length=55在位置5第3个位置是3111 1 2 3 4 5删除111(第⼀个元素):1 2 3 4 5删除5(末尾的元素)1 2 3 4删除第⼀个元素:2 3 4删除末尾的元素2 3 循环链表的实现（python）：其它部分与单链表相似#定义节点class Node:def__init__(self,data):self.data=dataself.next=Noneclass circleList:# 初始化头结点def__init__(self,n):self.head=Node(None)self.head.next=self.headself.n = n# 头插法建⽴链表-def listCreateForward(self):if self.n==0:return Falseelse:temp=self.headfor i in range(1,self.n+1):print('请输⼊第{0}个节点:'.format(i))num = input()node = Node(num)node.next=temp.nexttemp.next = node temp=temp.next# 尾插法建⽴链表def listCreateBackward(self):if self.n==0:return Falseelse:temp=self.headfor i in range(1,self.n+1):print('请输⼊第{0}个节点:'.format(i))num = input()node = Node(num)temp.next=nodetemp=nodetemp.next = self.head#读取循环链表def readList(self):if self.n==0:print("空链表！")else:temp = self.headwhile temp.next!=self.head: temp = temp.nextprint(temp.data,end='') linklist1=circleList(5)linklist1.listCreateForward()linklist1.readList()linklist1=circleList(5)linklist1.listCreateBackward() linklist1.readList()。
/*创建一个链表，实现对链表的创建，插入/追加，删除等操作*/# include <stdio.h># include <stdlib.h># include <malloc.h>//创建一个结构体typedef struct Node{int data;struct Node * pNext;}NODE,*PNODE;//函数前置声明PNODE create_list(void); //创建一个链表void traverse_list(PNODE); //遍历整个链表bool is_empty(PNODE); //判断列表是否为空int length_list(PNODE); //返回链表的长度bool insert_list(PNODE, int , int); //在链表中插入元素bool delete_list(PNODE, int, int *);//删除链表中的某个元素，并且返回被删除的元素的值。
void sort_list(PNODE); //对链表进行排序int main(void){//初始化头指针变量PNODE pHead = NULL;int val;//创建一个链表，将头结点的指针返回，保存到头指针变量中pHead = create_list();//判断这个链表是否为空/*if( is_empty(pHead) ){printf("这个链表为空\n");}else{printf("链表不为空\n");}*///查看元素的个数printf("该链表元素的个数为：%d\n",length_list(pHead));//遍历整个链表printf("遍历整个链表：");traverse_list(pHead);//插入元素printf("在第3个元素前插入一个99的值：");insert_list(pHead, 3, 99);traverse_list(pHead);//对链表进行排序printf("对链表进行升序排序：");sort_list(pHead);traverse_list(pHead);//删除链表中的元素printf("删除第三个位置的值：");delete_list(pHead, 3, &val);//遍历这个链表traverse_list(pHead);return 0;}/*常见一个链表@param void@return pHead 头指针*/PNODE create_list(void){int val; //用于保存用户输入的值int i; //for循环自增变量int data;//创建头结点PNODE pHead = (PNODE)malloc(sizeof(NODE));if(NULL == pHead){printf("动态内存创建失败\n");exit(-1);}PNODE pTail = pHead;pTail -> pNext = NULL;printf("需要创建元素的个数len=");scanf("%d",&val);for(i = 0; i < val; ++i){printf("请输入第%d个元素：", i + 1);scanf("%d",&data);//创建这个节点PNODE pNew = (PNODE)malloc(sizeof(NODE));if(NULL == pNew){printf("动态内存创建失败\n");exit(-1);}pNew -> data = data;pNew -> pNext = NULL;pTail -> pNext = pNew;pTail = pNew;}return pHead;}/*遍历一个链表@param PNODE 头指针@return void*/void traverse_list(PNODE pHead){PNODE p;p = pHead;if( is_empty(pHead) ){printf("这个链表为空\n");return;}while(NULL != p->pNext){p = p->pNext;printf("%d ",p->data);}printf("\n");}/*判断链表是否为空@param PNODE pHead 头指针@return bool*/bool is_empty(PNODE pHead){if( NULL == pHead -> pNext){return true;}else{return false;}}/*返回链表的长度@param PNODE pHead 头指针@return int i 指针的长度*/int length_list(PNODE pHead){PNODE p;int i = 0;if( is_empty(pHead) ){printf("链表为空。
C语⾔数据结构之线性表的链式存储结构1.什么是线性表的链式存储结构 —链表存储结点：包括元素本⾝的信息，还有元素之间的关系逻辑的信息这个结点有：数据域和指针域⼀个指针域：指向后继结点，单链表⼆个指针域：指向前继结点，还有⼀个指向后继结点双链表2.原理是：s=(LinkNode *)malloc(sizeof(LinkNode));//s->data=e; //这⾥赋值了s->next=p->next; //p->next=s; //这⾥把指针s给到了p结点a-> 结点b -> 结点c->结点d第⼀个数据：p->data ：a 对应的 p->next是存储地址为 007531F0第⼆个：p->data ：b 对应的 p->next是存储地址为：：00753200第三个数据：p->data ：c 对应的 p->next是存储地址为： 00753210…最后⼀个数据：p->data ：e 对应的 p->next是存储地址为：00000000这样在输出时：利⽤p=p->next进⾏循环p->next是第⼀个，p->next->next 是第⼆个p->next->next->next 是第三个while(p!=NULL){printf("%c",p->data);p=p->next;printf("地址变化：%p\n",p);}这⾥的循环使p=p->next.(⼀直指向下⼀个结点)while(j<i-1 && p!=NULL) //指针p不为空，当i=2,3,4,5执⾏下⾯语句{j++; //执⾏p=p->next; //// printf("%p",p);}#include<stdio.h>#include<malloc.h>typedef char ElemType;typedef struct LNode{ElemType data;struct LNode *next; //指针位置}LinkNode;bool ListInsert(LinkNode *&L,int i,ElemType e){int j=0;LinkNode *p=L,*s; //参数指针 P,s结构体指针，指针赋值，赋值的是地址 if(i<=0)return false;while(j<i-1 && p!=NULL) //指针p不为空，当i=2,3,4,5执⾏下⾯语句{j++; //执⾏p=p->next; //// printf("%p",p);}if(p==NULL)return false;else{s=(LinkNode *)malloc(sizeof(LinkNode));s->data=e; //这⾥赋值了s->next=p->next; //p->next=s; //这⾥把指针s给到了p.printf("%p\n",s->next);printf("%p\n",p->next);return true;}}void DispList(LinkNode *L){LinkNode *p=L->next; //这个L->next就是p->next，//不为空，// p->next指向了s, 返回 a,循环// p->next->next, ,指向了 b结点，引⽤的是 b// p->next->next->next ，指向c结点。
