一、顺序表
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)基于静态数组
1L.length = 0; //由系统自动回收空间
(2)基于动态数组
1free(L.data);
3、顺序表的插入
在顺序表L的第i个位置插入元素e,若i的输入不合法,返回false;插入成功,返回true;
顺序表的位序从1开始;在对顺序表操作时,是对数组进行操作,数组下标从1开始。
1
2
3
4
5
6
7
8
9
10
11
12bool 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
9bool 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
6int 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
4typedef 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
15LinkList 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
15LinkList 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
13LNode *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
6LNode *GetElem(LinkList L,int e){ LNode *p=L->next; while(p!=NULL&&p->data!=e) p=p->next; //遍历 return p; }
4、插入结点
5、删除结点
最后
以上就是结实小白菜最近收集整理的关于【数据结构基本代码】-----线性表的全部内容,更多相关【数据结构基本代码】-----线性表内容请搜索靠谱客的其他文章。
发表评论 取消回复