数据结构（C语言版）

2024-06-26 19:44| 来源: 网络整理| 查看: 265

#define MAXSIZE 100 //最大长度 typedef struct { ElemType *elem; //指向数据元素的基地址 int length; //线性表的当前长度 }SqList；

例子

#define MAXSIZE 10000 //图书表可能达到的最大长度 typedef struct //图书信息定义 { char no[20]; //图书ISBN char name[50]; //图书名字 float price; //图书价格 }Book; typedef struct { Book *elem; //存储空间的基地址 int length; //图书表中当前图书个数 }SqList; //图书表的顺序存储结构类型为SqList 线性表的重要基本操作

1. 初始化 2. 取值 3. 查找 4. 插入 5. 删除

初始化线性表L （参数用引用）

Status InitList_Sq(SqList &L){ //构造一个空的顺序表L L.elem=new ElemType[MAXSIZE]; //为顺序表分配空间 if(!L.elem) exit(OVERFLOW); //存储分配失败 L.length=0; //空表长度为0 return OK; }

初始化线性表L （参数用指针）

Status InitList_Sq(SqList *L){ //构造一个空的顺序表L L-> elem=new ElemType[MAXSIZE]; //为顺序表分配空间 if(! L-> elem) exit(OVERFLOW); //存储分配失败 L-> length=0; //空表长度为0 return OK; }

销毁线性表L

void DestroyList(SqList &L) { if (L.elem) delete[]L.elem; //释放存储空间 }

清空线性表L

void ClearList(SqList &L) { L.length=0; //将线性表的长度置为0 }

判断线性表L是否为空

int IsEmpty(SqList L) { if (L.length==0) return 1; else return 0; }

获取线性表L中的某个（第i 个）数据元素的内容

int GetElem(SqList L,int i,ElemType &e) { if (iL.length) return ERROR; //判断i值是否合理，若不合理，返回ERROR e=L.elem[i-1]; //第i-1的单元存储着第i个数据 return OK; }

在线性表L中查找值为e的数据元素

int LocateELem(SqList L,ElemType e) { for (i=0;i< L.length;i++) if (L.elem[i]==e) return i+1; //返回是第几个元素 return 0; }

在线性表L中第i个数据元素之前插入数据元素e

Status ListInsert_Sq(SqList &L,int i ,ElemType e){ if(iL.length+1) return ERROR; //i值不合法 if(L.length==MAXSIZE) return ERROR; //当前存储空间已满 for(j=L.length-1;j>=i-1;j--) L.elem[j+1]=L.elem[j]; //插入位置及之后的元素后移 L.elem[i-1]=e; //将新元素e放入第i个位置 ++L.length; //表长增1 return OK; }//见下图

（1）判断插入位置i 是否合法。（2）判断顺序表的存储空间是否已满。（3）将第n至第i 位的元素依次向后移动一个位置，空出第i个位置。（4）将要插入的新元素e放入第i个位置。（5）表长加1，插入成功返回OK。

若插入在尾结点之后，则根本无需移动（特别快）；若插入在首结点之前，则表中元素全部后移（特别慢）；若要考虑在各种位置插入（共n+1种可能）的平均移动次数，该如何计算？

将线性表L中第i个数据元素删除

Status ListDelete_Sq(SqList &L,int i){ if((iL.length)) return ERROR; //i值不合法 for (j=i;jdata=ai, 则p->next->data=ai+1

2.5.2 单链表基本操作的实现

1. 初始化 2. 取值 3. 查找 4. 插入 5. 删除

1.初始化(构造一个空表 )【算法步骤】（1）生成新结点作头结点，用头指针L指向头结点。（2）头结点的指针域置空。

Status InitList_L(LinkList &L){ L=new LNode; L->next=NULL;　　　　　 return OK; }

销毁

Status DestroyList_L(LinkList &L){ LinkList p; while(L) { p=L; L=L->next; delete p; } return OK; }

清空(链表仍在)

Status ClearList(LinkList & L){ // 将L重置为空表 LinkList p,q; p=L->next; //p指向第一个结点 while(p) //没到表尾 { q=p->next; delete p; p=q; } L->next=NULL; //头结点指针域为空 return OK; }

求表长

int ListLength_L(LinkList L){ //返回L中数据元素个数 LinkList p; p=L->next; //p指向第一个结点 i=0; while(p){//遍历单链表,统计结点数 i++; p=p->next; } return i; }

判断表是否为空

int ListEmpty(LinkList L){ //若L为空表，则返回1，否则返回0 if(L->next) //非空 return 0; else return 1;}

2. 取值（根据位置i获取相应位置数据元素的内容）

链表的查找：要从链表的头指针出发，顺着链域next逐个结点往下搜索，直至搜索到第i个结点为止。因此，链表不是随机存取结构

//获取线性表L中的某个数据元素的内容 Status GetElem_L(LinkList L,int i,ElemType &e){ p=L->next;j=1; //初始化 while(p&&jnext; ++j; } if(!p || j>i)return ERROR; //第i个元素不存在 e=p->data; //取第i个元素 return OK; }//GetElem_L //在线性表L中查找值为e的数据元素 int LocateELem_L (LinkList L，Elemtype e) { //返回L中值为e的数据元素的位置序号，查找失败返回0 p=L->next; j=1; while(p &&p->data!=e) {p=p->next; j++;} if(p) return j; else return 0; }

3. 插入（插在第 i 个结点之前）

//在L中第i个元素之前插入数据元素e Status ListInsert_L(LinkList &L,int i,ElemType e){ p=L;j=0; while(p&&jnext;++j;} //寻找第i−1个结点 if(!p||j>i−1)return ERROR; //i大于表长 + 1或者小于1 s=new LNode; //生成新结点s s->data=e; //将结点s的数据域置为e s->next=p->next; //将结点s插入L中 p->next=s; return OK; }//ListInsert_L

5. 删除（删除第 i 个结点）

//将线性表L中第i个数据元素删除 Status ListDelete_L(LinkList &L,int i,ElemType &e){ p=L;j=0; while(p->next &&jnext; ++j; } if(!(p->next)||j>i-1) return ERROR; //删除位置不合理 q=p->next; //临时保存被删结点的地址以备释放 p->next=q->next; //改变删除结点前驱结点的指针域 e=q->data; //保存删除结点的数据域 delete q; //释放删除结点的空间 return OK; }//ListDelete_L

单链表的建立（前插法）

void CreateList_F(LinkList &L,int n){ L=new LNode; L->next=NULL; //先建立一个带头结点的单链表 for(i=n;i>0;--i){ p=new LNode; //生成新结点 cin>>p->data; //输入元素值 p->next=L->next;L->next=p; //插入到表头 } }//CreateList_F

单链表的建立（尾插法）

void CreateList_L(LinkList &L,int n){ //正位序输入n个元素的值，建立带表头结点的单链表L L=new LNode; L->next=NULL; r=L; //尾指针r指向头结点 for(i=0;i>p->data; //输入元素值 p->next=NULL; r->next=p; //插入到表尾 r=p; //r指向新的尾结点 } }//CreateList_L 2.5.3 循环链表

对循环链表，有时不给出头指针，而给出尾指针可以更方便的找到第一个和最后一个结点

开始结点：rear->next->next终端结点：rear

循环链表的合并

2.5.4 双向链表 typedef struct DuLNode{ ElemType data; struct DuLNode *prior; struct DuLNode *next; }DuLNode, *DuLinkList

双向链表的插入

Status ListInsert_DuL(DuLinkList &L,int i,ElemType e){ if(!(p=GetElemP_DuL(L,i))) return ERROR; s=new DuLNode; s->data=e; s->prior=p->prior; p->prior->next=s; s->next=p; p->prior=s; return OK; }

双向链表的删除

Status ListDelete_DuL(DuLinkList &L,int i,ElemType &e){ if(!(p=GetElemP_DuL(L,i))) return ERROR; e=p->data; p->prior->next=p->next; p->next->prior=p->prior; delete p; return OK; }

总结

【本文地址】

公司简介

联系我们