avatar

数据结构与算法-CH2-线性表

线性表

概念

定义:由n(n$\geq$0)个性质相同的数据元素组成的有限序列,n称为线性表的长度

特点:

  • 存在唯一的一个被称作 “ 第一个 ” 的数据元素;
  • 存在唯一的一个被称作 “ 最后一个 ” 的数据元素;
  • 除第一个之外,结构中的每个数据元素均只有一个前驱;
  • 除最后一个之外,结构中的每个数据元素均只有一个后继;

ADT表达式

ADT List is 
operations
List SetNullList(void) 创建一个空的线性表
int IsNull(List list) 判断线性表list是否为空
int InsertPre(List list,position p,Datatype x) 在第p个位置之前插入元素x
int InsertPost(List list,position p,Datatype x) 在第p个位置之后插入元素x
int DelIndex(List list, position p) 删除线性表中第p个位置的元素
int DelValue(List list,Datatype x) 删除线性表中值为x的元素
int LocateIndex(List list,Datatype x) 在线性表中查找值为x的元素位置
int LocatePos(List list,Datatype x) 在线性表中查找值为x的元素在内存中的位置
End ADT List

顺序表

基本概念

通过位置表示数据之间的关系,存放在一片连续的存储区域,如编程语言中的数组。

这里通过一个具体的实例(书上的):

//gcc version 5.4.0 20160609 
//(Ubuntu 5.4.0-6ubuntu1~16.04.12))
#include <stdio.h>

struct List //1-定义程序表类型
{
//2-定义顺序表成员变量
int Max;
int n;
int *elem;
};

int main()
{
printf("size of int: %d\n",sizeof(int));
printf("size of List: %d\n",sizeof(List));
return 0;
}

输出

joe1sn@MSI:/mnt/d/Study/大二(上)/数据结构与算法$ ./List
size of int: 4
size of list: 16

**注:**在反汇编时,除非程序调用了结构体的成员,不然我们是无法看出结构体的

我们简单的给这个结构体赋值

//3-使用该变量	
List *seqlist = (List*)malloc(sizeof(List));
seqlist->Max=10;
seqlist->n=0;
seqlist->elem = (int*)malloc(sizeof(int) * (seqlist->Max));
for (int i = 0; i < 5; ++i)
{
seqlist->elem[i]=i*i;
(seqlist->n)++;
}

进入gdb调试

  • 结构体分配结束数组成员分配结束

    结构体地址:0x603010

    数组地址:0x603030

    0nNuTO.png

  • for循环结束

    虽然是64位程序,但是我们的成员都是4字节大小的,所以这里按照32解析

    0nNwtg.png

    0x603020那一行,我们申请的List空间变成这样

    Max=0xa;
    n=0x5;
    elem=0x603040; //ptmalloc分配有0x10的文件头大小
    elem[0xa]={0x0,0x1,0x4,0x9,0x10,0x0,0x0,0x0,0x0,0x0};

综上,创造一个顺序表的顺序:

  • 1-定义程序表类型;
  • 2-定义顺序表成员变量;
  • 3-使用该变量

规范的操作

开始枯燥的搬代码

先创建一个全局的指针

typedef struct List* SeqList;

顺序表的建立

SeqList SetNullList_Seq(int m)
{
//1-申请结构体空间
SeqList slist=(SeqList)malloc(sizeof(List));
//2-验证空间申请是否成功
if (slist)//2-1成功
{
//3-对elem数组申请空间
slist->elem = (int *)malloc(sizeof(int)*m);
if (slist->elem) //3-1验证elem数组是否申请成功
{
slist->Max=m;
slist->n=0;
return slist;
}
else //3-2申请失败
{
printf("Alloc elem failed\n");
free(slist);
*slist = 0;
}
}
else
{
printf("Alloc failure!\n");
return NULL;
}
}

判断顺序表为空

int IsNullList_seq(SeqList slist)
{
return slist->n;
}

顺序表的插入

int InsertPre_seq(SeqList slist, int p, DataType x)
{
//在线性表slist的p位置之前插入x,成功返回1,否则返回0
int q;
if(slist->n >= slist->Max)
{
//顺序表满溢出
printf("overflow");
return 0;
}
if(p<0 || p>slist->n)
{ //不存在下标为p的元素
printf("not exist!\n");
return 0;
}
//插入位置以及之后的元素后移
for (q = slist->n - 1; q >= p; q--)
slist->elem[q+1] = slist->elem[q];
slist->elem[p] = x; //插入元素x
slist->n = slist->n + 1; //顺序表长度加1
return 1;
}

顺序表的删除

int DelIndex_seq(SeqList slist ,int p) //删除下标为p的元素
{
int q;
if(p<0||p>=slist->n)
{
//不存在下标为p的元素
printf("Not exist\n");
return 0;
}
for (q = p; q<slist->n-1; q++)
//下标p之后的元素向前移动
slist->elem[q]=slist->elem[q+1];
//顺序表长度减1
slist->n = slist->n - 1;
return 1;
}

顺序表的查找

1.顺序查找
//查找值为x的元素,返回元素所在下标
int LocateIndex_seq(SeqList slist, int x)
{
int q;
for(q=0;q<slist->n;q++)
{
if (slist->elem[q] == x)//查找成功,返回对应的下标
return q;
}
return -1;//查找失败,返回-1
}
2.二分查找
//基于循环
int binsearch(SeqList slist, int key, int *pos)
{
int index = 1;
int mid;
int low = 0;
int high = (slist->n) - 1;
while (low <= high)
{
mid = (low + high) / 2;
if (slist->elem[mid] == key) {
*pos = mid;
printf("找到,共进行%d次比较\n", index);
printf("要找的数据%d在位置%d上\n", key, mid);
return 1;
}
else if (slist->elem[mid] > key)
high = mid - 1;
else low = mid + 1;
index++;
}
*pos = low;
printf("没有找到,共进行%d次比较\n", index-1);
printf("可将此数插入到位置%d上\n", *pos);
return -1;
}
//基于递归
int binsearch(SeqList slist, int key, int high, int low, int *pos)
{
int mid;
if (low<=high)
{
mid=(low+high)/2;
if (slist->elem[mid]==key)
{
printf("要找的数据%d在位置%d上\n", key, mid);
return 1;
}
if (slist->elem[mid]<key)//小于取小的一侧
{
*pos=mid;
return binsearch(slist, key, high, low, pos);
}
else if (slist->elem[mid]<key)//大于取大的一侧
{
*pos=mid+1;
return binsearch(slist, key, high, low, pos);
}
}
printf("没有找到,共进行%d次比较\n", index-1);
return -1;
}

链表

杨毅NB好吧

这里还没上,就先按自己的讲讲

0x1 定义结构体

struct node
{
int n; //数据域.可以有多个数据域
struct node *next; //结构体内有一个指向,可指向本类结构变量。
};

0x2 链表初始化

//开辟一个新结点,让head指向它
struct node *head = (struct node*)malloc(sizeof(struct node);
struct node *p0; //始终指向前一个结点
struct node *p1; //指向有效数据的新节点
p0 = head; //p0为初始点,以为将开始新建节点
int n;

0x3 输入链表

while(1)
{
cout<<"enter '-1' to quit\n";
cout<<"Please input> ";
cin>>n;
if (n==-1) //数据为-1则退出
break;
else
{
//将p1指向有效数据新的节点
p1 = (struct node*)malloc(sizeof(struct node));
p1->n = n;

//每一个新结点暂时都当成是最后一个结点
p1->next=NULL;

//上一个节点指针指向该节点,为交换做准备
p0->next=p1;

//p0指向前一个结点,将开始新建节点
p0 = p0->next;
}
}

0x4 输出链表

p0 = head;
while(p0->next!=NULL) //只有head的next域为NULL
{
p0 = p0->next;
cout<<p0->n<<" ";
}

0x5 完整代码

#include <iostream>
#include <cstdlib>
using namespace std;
struct node
{
int n;
struct node *next;
}node;

int main()
{
//开辟一个新结点,让head指向它
struct node *head;
head = (struct node *)malloc(sizeof(struct node));
struct node *p0; //始终指向前一个结点
struct node *p1; //指向有效数据的新节点
p0 = head; //p0为初始点,以为将开始新建节点
int n;
while(1)
{
cout<<"enter '-1' to quit\n";
cout<<"Please input> ";
cin>>n;
if (n==-1) //数据为-1则退出
break;
else
{
//将p1指向有效数据新的节点
p1 = (struct node*)malloc(sizeof(struct node));
p1->n = n;

//每一个新结点暂时都当成是最后一个结点
p1->next=NULL;

//上一个节点指针指向该节点,为交换做准备
p0->next=p1;

//p0指向前一个结点,将开始新建节点
p0 = p0->next;
}
}
cout<<"Now to output the list\n";

p0 = head;
while(p0->next!=NULL) //只有head的next域为NULL
{
p0 = p0->next;
cout<<p0->n<<" ";
}
cout<<endl;
return 0;
}

大致流程图以及链表结构

node.png

gdb调试

Continuing.
enter '-1' to quit
Please input> 1
enter '-1' to quit
Please input> 2
enter '-1' to quit
Please input> 3
enter '-1' to quit
Please input> 4
enter '-1' to quit
Please input> 5
enter '-1' to quit

**注:**要减去0x10的结构体头部

0ncNB4.png

刚好形成了5个chunk的单向链表

Author: Joe1sn
Link: http://blog.joe1sn.top/2020/%E7%AC%AC%E4%BA%8C%E7%AB%A0-%E7%BA%BF%E6%80%A7%E8%A1%A8/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Donate
  • 微信
    微信