其他文章：
数据结构之栈和队列
文章目录
1.1 概念
1.2 顺序表
1.3 链表
1.4 两种存储方式的比较
1.5 两种表的实现方式及其各种操作
1.5.1 顺序表
1.5.2 单链表
1.6 应用实例
1.1 概念
线性表是具有相同特性的数据元素的一个有限序列。
注：注意概念中的关键字，线性表中的每一项叫数据元素，它是有限的。另外值得注意的是，线性表是可以是空表，即它的长度是0时为空表。
数据结构中，线性表分为顺序表和链表。
下面介绍两种存储形式的概念的特性以及两者之间的比较。
1.2 顺序表
顺序表就是把线性表中的所有元素按照其逻辑顺序，依次存储到从指定的存
储位置开始的一块连续的存储空间中。
注：说白了，在C语言中，就是数组，而数组的特点就是一块连续的存储空间。所谓的逻辑顺序，按照我的理解，就是其排列的顺序。或从小到大或者从大到小或者乱序，或者按照某个特定的规则排序。（不知道有没有理解到位！！！！）
1.3 链表
在链表存储中，每个节点不仅包含所有元素本身的信息，还包含元素之间逻辑关系的信息，即前驱节点包含后继节点的地址信息。
1.4 两种存储方式的比较：
1、顺序表的特点：
1）随机访问特性。顺序表在查找方面效率较高，只要知道下标，立马就能获取到该元素。
2）顺序表要求占用连续的存储空间。这是顺序表的存储结构决定的，它用数组表示，就必须是占用连续的存储空间。
3）存储分配只能预先进行，即静态分配。就像C语言中数组的声明一样，需要在声明的时候就需要确定其长度，例如int a[30];长度为30的int型数组。
2、链表的特点
1）不支持随机访问。因为链表中每个元素的地址保存在其前驱节点中的指针域，所以要访问该节点，必须知道其前驱节点，所以访问节点每次都是从头结点开始。
2）节点的存储空间利用率较顺序表稍低一些。
3）动态分配存储空间。链表可以任意增加链表长度和缩短链表长度，这得益于它的结构特点：链式。
注：顺序表在做插入操作时需要移动多个元素，而链表则不需要移动任何元素。
1.5 两种表的实现方式及其各种操作
首先定义几个常量，代码如下（C/C++）：
#define MAXSIZE 100 //线性表的最大长度
#define DataType int //数据的类型
1.5.1 顺序表
线性表的定义只有两个数据域，一个是存储数据信息的数组，一个是保存线性表长度的length变量。代码如下：
typedef struct {
DataType data[MAXSIZE]; //数据域
int length; //顺序表长度
}SqList;
以下是顺序表的各种操作
1.初始化操作
顺序表的初始化操作只需要将length初始化为0即可.代码如下:
void Init(SqList &L){
L.length = 0;
}
2、插入操作
插入操作可分为以下几步(顺序表的存储开始位置为1):
(1) 判断插入位置index的合法性以及length的合法性(也可以增加顺序表的最大长度).
(2)将第index个元素的后续元素后移一位.
(3)将e值插入index位置,并将length加1.
int Insert(SqList &L, int index, DataType e) {
//首先判断index的合法性
//1 <= index <= length + 1, 元素开始下标为1,可以插入顺序表尾部
//L表的长度也有限制，必须小于定义的长度 MAXSIZE - 1
if(index < 1 || index > L.length + 1 || L.length == MAXSIZE - 1) {
return 0; //插入失败返回0
}
int i;
//参数合法，开始插入操作
//1、先将需要移动的元素移动
for(i = L.length; i >= index; --i) {
L.data[i + 1] = L.data[i];
}
//2、最后index位置空着，将e插入
L.data[index] = e;
//3、长度加1
L.length++;
return 1; //插入成功，返回1
}
3.删除操作
删除操作可分为以下几步:
(1) 判断插入位置index的合法性.
(2)将第index个元素的后续元素前移一位.
(3)将e值插入index位置,并将length减1.
int Delete(SqList &L, int index, DataType &e) {
//index的合法性
//index的范围是1 <= index <= L.length
if(index < 1 || index > L.length) {
return 0; //删除失败,返回0
}
//1.找到要删除的元素并赋给e
e = L.data[index];
//2.将第index元素的后面的元素前移一位
int i;
for(i = index + 1; i <= L.length; i++) {
L.data[i - 1] = L.data[i];
}
//3.顺序表的长度减1
L.length--;
}
4.定位操作
因为顺序表是从下标为1的位置开始存储,所以可以作如下判断,查找元素值为e的顺序表中的元素时,若查找失败返回0,查找成功返回下标,成功时下标>0.代码比较简单,如下:
int LocateElem(SqList L, DataType e) {
int i;
for(i = 1; i <= L.length; i++) {
if(L.data[i] == e) {
return i; //查找成功，返回i
}
}
return 0; //若查找失败，返回0
}
5.遍历操作
遍历操作很简单,代码如下:
void Traverse(SqList L) {
for(int i = 1; i <= L.length; i++) {
printf(" %d", L.data[i]);
}
}
6.判断顺序表是否为空
顺序表是否为空只需要根据length的值判断即可,代码如下:
int IsEmpty(SqList L){
if(L.length > 0){
return 1;
}
return 0;
}
顺序表的实现算是比较简单的.可以加入自动增长顺序表空间的功能,只需要判断是否已经满了,若满了,只需要另外开辟一个增长的空间即可.此时顺序表的结构体需要换成指针式的.具体的代码,可以见数据结构课本.或者下载完整的代码,我将会在博客最后贴出.
下面看看链表的存储结构和各种操作实现.
1.5.2 单链表
先定义两个数据类型:
typedef int ElemType; //数据类型
typedef int Status; //返回值类型
单链表的定义也只有两个域,即数据域和指针域,数据域保存当前节点的数据,可以多种(代码为整形变量),指针域保存下一个节点的地址.具体代码如下:
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode, *LinkedList;
以下是单链表的各种操作
1.初始化操作:
初始化操作是生成一个头结点,并将头结点的next值赋值为NULL即可,代码如下:
Status Init(LinkedList &head) {
head = (LinkedList) malloc(sizeof(LNode));
if (!head)return ERROR;
head->next = NULL;
return OK;
}
2.插入操作:
插入操作要考虑的因素有以下几点:
(1)插入的位置的合法性
(2)单链表因为其特点,插入操作比较简单,只需要修改指针即可,所以难点是在插入位置的判断上.代码如下:
Status Insert(LinkedList &L, int i, ElemType e)
LinkedList p = L;
LinkedList s; //待插入节点
int j = 0; //j=0时,p指向头结点
//找到第i个节点的位置,循环结束之后,p指向第i-1个元素
while (p && j < i - 1) {
p = p->next;
++j;
}
//若i小于1,或者i大于链表长度+1
//i小于1时,循环之后j > i - 1
//若i > 长度+1,那么最后p指向的是NULL,而本应该指向的是第i-1个元素
if (!p || j > i - 1)return ERROR;
//为新节点开辟内存空间
s = (LinkedList) malloc(sizeof(LNode));
//将新元素插入其中
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}
3.删除操作
删除操作原理同上.需要注意的是,删除元素的i的范围不一样.因为不能删除第length+1个元素,因为不存在.
Status Delete(LinkedList &L, int i, ElemType &e) {
LinkedList q, p = L;
int j = 0;
while (p && j < i - 1) {//find the No. i-1 LNode
p = p->next;
++j;
}
if (!p || j > i - 1)return ERROR;
//if L has element[i], p->next is now point to it.
q = p->next;
p->next = q->next;
e = q->data;
free(q);
return OK;
}
4.获取元素
获取元素的原理也同上,需要注意的是,同插入不同.获取元素的范围和删除时一样.以下代码因为p和j的初始值不一样,所以后面的判断也是不一样的,需要注意.代码如下:
Status GetElem(LinkedList &L, int i, ElemType &e) {
LinkedList p = L->next; //这里开始指向的是第一个节点
int j = 1;//所以j也要相应的指向第一个节点
while (p && j < i) {
p = p->next;
++j;
}
if (!p || j > i)return ERROR;
e = p->data;
return OK;
}
5.一个重要但是简单的操作就是遍历操作.代码如下:
Status Traverse(LinkedList &L) {
int count = 0;
LinkedList p = L->next;
while (p) {
count++;
cout << p->data << " ";
p = p->next;
}
}
6.下面介绍两个重要的操作,就是尾插法和头插法建立单链表的操作.
头插法,即在头部插入元素,就是每个元素插入之后,会在链表的第一的位置,所以头插法建立的单链表是倒序的.
头插法关键步骤:
(1)建立新的节点保存待插入元素.
(2)将此节点的指针域(next指针指向头元素,即第一个元素,即p->next = head->next;).
(3)将头指针指向p节点(新建立的节点),即head->next = p;.
头插法代码如下:
//create a length's LinkedList by head insert method
//this method causes a reversed sequence.
void CreateListHead(LinkedList &L, int length) {
//first, create a null LinkedList with a head node
L = (LinkedList) malloc(sizeof(LNode));
L->next = NULL;
LinkedList p;
//input the array that will be inserted.
cout << "Please enter " << length << " numbers." << endl;
ElemType e[length];
for (int i = 0; i < length; i++) {
cin >> e[i];
}
//create node and insert into head->next
for (int i = 0; i < length; i++) {
p = (LinkedList) malloc(sizeof(LNode));
p->data = e[i];
//insert
p->next = L->next;
L->next = p;
}
}
尾插法和头插法正好相反,是在尾部插入,顺序是正的.
尾插法的关键步骤如下:
(1)建立一个指向末尾元素的指针,r,初始指向头结点,随着元素的插入,每次都指向末尾元素.
(2)建立一个新的元素p,用于保存插入的元素.
(3)对p赋值之后接入链表末尾,即r->next = p;
(4)更新r的位置,即r = p;.
尾插法的代码如下,需要注意一些细节:
//create a length's LinkedList by rear insert method
//this method causes a normal order sequence.
void CreateListRear(LinkedList &L, int length) {
//first, create a null LinkedList with a head node
L = (LinkedList) malloc(sizeof(LNode));
//declare a new LinkedList which point to L(null at first)
//r point to the end of L when inserting.
LinkedList r = L;
//input the array supposed to be inserted.
cout << "Please enter " << length << " numbers." << endl;
ElemType e[length];
for (int i = 0; i < length; i++) {
scanf("%d", &e[i]);
}
LinkedList p;
//create node and insert into head->next
for (int i = 0; i < length; i++) {
p = (LinkedList) malloc(sizeof(LNode));
p->data = e[i];
//insert
r->next = p;
r = p;
}
r->next = NULL;//the pointer of the last elem. must be NULL.
}
1.6 应用实例
至此,顺序表的单链表的存储结构和基本操作已经整理完毕.下面给出两个个例题,作为操练:
(1)请逆序打印出单链表的所有元素,假设初始时,L指针指向单链表的开始节点.
解析:开始时指向第一个节点,那么需要逆序打印的话可以考虑用递归的方法.参考代码如下:
void print(LinkedList &L){
if(L != NULL){
print(L->next);
printf("%d ", L->data);
}
}
(2)有一个int型数组,里面保存的是个位数的int数据(即0~9的数字), N <= 9, 数组的长度为N,另给出一个int i, 不能使用其他变量,设计一个算法,求出数组中的最小者.
解析:意思是,只能用数组本身和i变量,求出其最小值.下面给出一个以前常用的一个求数组最小值的算法,如下:
#include <iostream>
#include <stdio.h>
using namespace std;
#define N 10
int main() {
int a[N];
for(int i = 0; i < N; i++) {
scanf("%d", &a[i]);
}
int min1 = a[0];
for(int j = 1; j < N; j++) {
if(a[j] < min1) {
min1 = a[j];
}
}
cout << min1 << endl;
return 0;
}
从以上代码可以看出,需要找出最小值,必须有一个保存当前循环的最小值的变量,而题目只给了一个i,所以i必须分成两半用.
重新研究题目意思可以知道,数组保存的数据是一个个位数,也就是说是一个十位数是0的数,可以这样分开i,用i的十位数保存当前的循环,i的个位数保存当前的最小值,因为最小值为个位数,所以i可以完成保存两个变量的使命,参考代码如下,注释已经很详细了:
void FindMin(int a[], int &i){
i = a[0]; //初始时保存第一个数
while(i / 10 < N){
//循环继续的条件,初始时i = a[0],十位为0, 每次循环之后对十位加1即可.
if(i % 10 > a[i/10]){
//用i个位上的数字,即当前最小值,和a中第i/10(i的十位数,即当前比较的a数组元素的下标)个数.
//若a[..]更小,则更新i的个位数字
i = i - i % 10;
i = i + a[i/10];
}
i += 10;//即十位上数字加1,进入下一个比较.
}
i = i % 10;//获取个位上的数字,即最小值
}
今天就到这里了,完整的代码后续会更新此到这里.谢谢~~~~
