线性表
线性表的顺序表示和实现
初始化
步骤:
- 为顺序表L动态分配一个预定义大小的数组空间,使elem指向这段空间的基地址
- 将表的当前长度设为0
代码:
1
2
3
4
5
6
7
8
9
10
11//初始化
const int MAXSIZE = 100;
bool InitList(SqList L)
{
L.elem = new ElemType[MAXSIZE];
if(!L.elem){
return 0;
}
L.length = 0;
return true;
}取值
步骤:
- 判断指定的位置序号i的值是否合理$$(1<=i<=L.length)$$,若不合理,返回false
- 若值合理,则将第i个数据元素L.elem[i-1]赋值参数e,通过e返回第i个数据元素的传值
1
2
3
4
5
6
7
8
9//取值
int GetElem(SqList L,int i,ElemType e)
{
if(i<1 || i>L.length){
return -1;
}
e=L.elem[i-1];
return e;
}查找
步骤:
- 从第一个元素起,依次将其值和e比较,若找到和e值相等的元素L.elem[i],则查找成功,返回该元素的序号i+1
- 若查遍整个顺序表都没有找到,则查找失败,返回0
1
2
3
4
5
6
7
8
9
10
11
12//查找
int LocateElem(SqList L,ElemType e)
{
for(int i=0;i<L.length;i++){
if(e==L.elem[i]){
return i+1;
}else{
return 0;
}
}
return 0;
}插入
- 判断插入位置i是否合法(i值的合法范围为1<=i<=n+1),若不合法返回FALSE
- 判断顺序表的存储空间是否已满,若满了,返回FALSE
- 将第n个至第i个元素依次向后移动一个位置,空出第i个位置(i=n+1时无序移动)
- 将要插入的元素e放入第i个元素
- 表长加一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17//插入
bool ListInsert(SqList &L,int i,ElemType e)
{
if(i<1 || i>L.length+1)
{
return false;
}
if(L.length==MAXSIZE){//判断顺序表的存储空间是否已满
return false;
}
for(int j=L.length-1;j>=i-1;j--){
L.elem[j+1]=L.elem[j];
}
L.elem[i-1] = e;
++L.length;
return true;
}删除
步骤:
- 判断删除位置i是否合法(合法的值为1<=i<=n),若不合法则返回FALSE
- 将第i+1个元素至第n个元素依次向前移动一个位置(i=n时无需移动)
- 表长减一
1
2
3
4
5
6
7
8
9
10
11
12//删除
bool ListDelete(SqList &L,int i)
{
if(i>L.length && i<1){
return false;
}
for(int j=i;j<=L.length-1;j++){
L.elem[j-1]=L.elem[j];
}
--L.length;
return true;
}
测试:
1 |
|
运行:
线性表的链式表示和实现
单链表
初始化
- 生成新节点作为头结点,用头指针L指向头结点
- 头结点的指针域置空
1 | void Initlist(LinkList &L) |
取值
- 用指针p指向首元结点,用j做计数器初值赋为1
- 从首元结点开始依次顺着链域next向下访问,只要指向当前节点的指针p不为空(NULL),并且没有到达序号为i的节点,则循环执行以下操作:
- p指向下一节点
- 计数器j加一
- 退出循环时,如果指针p为空,或者计数器j大于i,说明指定的序号i值不合法(i大于表长n或i小于等于0),取值失败返回ERROR;否则取值成功,此时j=i时,p所指的节点就是要找的第i个节点,用参数e保存当前节点的数据域,返回OK
1
2
3
4
5
6
7
8
9
10
11
12
13
14bool GetElem(LinkList &L, int i, int &e) {
int j;
LinkList p;
p = L->next;
j = 1;
while (j < i && p) {
p = p->next;
j ++;
}
if (!p || j > i)
return false;
e = p -> data;
return true;
}查找
- 用指针p指向首元结点
- 从首元结点开始依次顺着链域next向下查找,只要指向当前节点的指针p不为空,并且p所指节点的数据域不等于给定值e,则循环执行以下操作:p指向下一节点
- 返回p。若查找成功,p此时指向节点的地址值;若查找失败,则p的值为NULL
1
2
3
4
5
6
7
8
9bool LocateElem(LinkList &L, int e) {
LinkList p;
p = L-> next;
while (p && p->data != e)
p = p->next;
if (!p)
return false;
return true;
}插入
- 查找节点ai-1并由指针p指向该节点
- 生成一个新节点*s
- 将新节点*s的数据域置为e
- 将新节点*s的指针域指向节点ai
- 将节点*p的指针域指向新节点*s
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17bool ListInsert(LinkList &L, int i, int e) {
int j;
LinkList p, s;
p = L;
j = 0;
while (p && j < i - 1) {
p = p->next;
j++;
}
if (!p || j > i - 1)
return false ;
s = new LNode;
s->data = e;
s->next = p->next;
p->next = s;
return true;
}删除
- 查找节点ai-1并由指针p指向该节点
- 临时保存待删除的节点ai的地址在q中,以备释放
- 将节点*p的指针域指向ai的直接后继节点
- 释放节点ai的空间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15bool ListDelete(LinkList &L, int i) {
LinkList p, q;
int j = 0;
p = L;
while ((p->next) && (j < i - 1)) {
p = p->next;
j ++;
}
if (!(p->next) || (j > i - 1))
return false;
q = p->next;;
p->next = q->next;
delete q;
return true;
}创建单链表
前插法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15void CreateList_H(LinkList &L)
{
int n ;
LinkList s;
L = new LNode;
L ->next = NULL;
while(n--)
{
s = new LNode ;
cin>>s->data;
s->next = L->next;
L->next = s;
}
}后插法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21void CreateList_R(LinkList &L) //尾插法创建单链表 (尾插法是正序建表)
{
//输入n个元素,建立到头结点的单链表
int n ;
LinkList s, r;
L = new LNode;
L->next = NULL; //先建立一个带头结点的空链表
r = L; //尾指针r指向头结点 (就他自己)
cout<<"请输入元素个数 n: "<<endl;
cin>>n;
cout<<"请依次输入n个元素:"<<endl;
cout<<"前插法创建单链表..."<<endl;
while(n--)
{
s = new LNode ; //生成新结点s
cin>>s->date; //输入元素赋值给新结点的数据域
s->next = NULL;
r->next = s; //将新结点插s插入尾结点*r之后
r = s; //r指向新的尾结点s
}
}
循环链表
双向链表
顺序表和链表的比较
空间性能
时间性能
This is Tab 1.
This is Tab 2.
This is Tab 3.
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 活在当下的博客!
评论