我是靠谱客的博主 结实小白菜,这篇文章主要介绍【数据结构基本代码】-----线性表,现在分享给大家,希望可以做个参考。

一、顺序表

1、顺序表的定义

(1)基于静态数组

复制代码
1
2
3
4
5
#define Maxsize 50 typedef struct{ Elemtype data[Maxsize]; int length; }SeqList

(2)基于动态数组

复制代码
1
2
3
4
5
6
7
8
9
#define InitSize 100 typedef struct{ Elemtype *data; //data指针指向第一个元素的位置 int length; int Maxsize; }SeqList L.data=(Elemtype *)malloc(sizeof(Elemtype)*InitSize);

2、顺序表的销毁

(1)基于静态数组

复制代码
1
L.length = 0; //由系统自动回收空间

(2)基于动态数组

复制代码
1
free(L.data);

3、顺序表的插入

在顺序表L的第i个位置插入元素e,若i的输入不合法,返回false;插入成功,返回true;

顺序表的位序从1开始;在对顺序表操作时,是对数组进行操作,数组下标从1开始。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
bool ListInsert(SeqList &L, int i, Elemtype e){ if(i<1 || i>L.length+1) return false; if(L.length>=MaxSize) return false; for(int j=length;j>=i,j--){ L.data[j]==L.data[j-1]; } L.data[i-1]=e; L.length++; return true; }

最好情况:在表尾插入,不需要移动元素,时间复杂度为O(1);

最坏情况:在表头插入,需要移动n个元素,时间复杂度为O(n);

平均时间复杂度为O(n)。

4、顺序表的删除

删除顺序表第i个元素,用引用变量e返回。

复制代码
1
2
3
4
5
6
7
8
9
bool Listdel(SeqList &L, Elemtype &e, int i){ if(i<1 || i>length) return false; e=L.data[i-1]; //先将data[i-1]赋值给e再删除 for(int j=i;j<=L.length-1,j++) L.data[j-1]=L.data[j]; L.length--; return true; }

最好情况:删除表尾元素,不需要移动元素,时间复杂度为O(1);

最坏情况:删除表头元素,需要移动n-1个元素,时间复杂度为O(n);

平均时间复杂度为O(n)。

5、顺序表的查找

(1)按序号查找,由于顺序表随机存取的特性,按序号查找元素的时间复杂度为O(1)。

(2)按值查找

在顺序表L中查找第一个值为e的元素,并返回其位序。

复制代码
1
2
3
4
5
6
int Locate(SeqList L,Elemtype e){ for(int i=0;i<length;i++){ if(L.data[i]==e) return i+1; //查找成功返回位序 return 0; //退出循环,查找失败 }

最好情况:查找的元素就在表头,时间复杂度O(1);

最坏情况:查找的元素在表尾,需要遍历整个顺序表,时间复杂度O(n);

平均时间复杂度O(n)。

二、单链表

1、单链表的定义

复制代码
1
2
3
4
typedef struct{ Elemtype data; struct LNode *next; }LNode,*LinlList;

2、单链表的创建

(1)头插法

  元素的插入顺序与在单链表中的顺序相反,因此可以利用头插法实现链表的逆置。

步骤:

a:初始化一个单链表(创建一个头结点,并将该单链表置为空)

b:输入结点的data值,同时也要为每个data值建立一个结点。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
LinkList Headinsert(LinkList &L){ //不用再声明L,L不是变量 L=(LinkList)malloc(sizeof(LNode)); //头结点为LinkList,用来表示该结点为头结点 L->next=NULL; LNode *q; int x; scanf("%d",&x); whlie(x!=-1){ q=(LNode*)malloc(sizeof(LNode)); //普通结点用LNode* q->data=x; q->next=L->next; //顺序不能颠倒,否则会断链 L->next=q; } return L; }

(2)尾插法

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
LinkList endInsert(LinkList &L){ L=(LinkList)malloc(sizeof(LNode)); LNode *q; LNode *r=L; int x; scanf("%d",&x); while(x!=-1){ q=(LNode*)malloc(sizeof(LNode)); q->data=x; r->next=q; r=q; } r->next=NULL; return L; }

3、查找

(1)按序号查找

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
LNode *GetElem(LinkList L,int i){ if(i<0) return NULL; if(i==0) return L; LNode *p=L->next; while(p&&j<i) //p!=NULL且j<i p=p->next; //遍历不是由于j++,而是由于p=p->next,随着j++,最后j=i时退出循环 j++; } return p; //返回的不是位序,而是查找到的结点 }

(2)按值查找

复制代码
1
2
3
4
5
6
LNode *GetElem(LinkList L,int e){ LNode *p=L->next; while(p!=NULL&&p->data!=e) p=p->next; //遍历 return p; }

4、插入结点

5、删除结点

最后

以上就是结实小白菜最近收集整理的关于【数据结构基本代码】-----线性表的全部内容,更多相关【数据结构基本代码】-----线性表内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(74)

评论列表共有 0 条评论

立即
投稿
返回
顶部