赞
踩
目录
线性表的定义是n个相同类型的数据元素的有限序列,在初学C语言时,我们使用的字符串就可以看成一种线性表,线性表在逻辑上是一条直线,但在物理结构上可能并不是连在一起的。常见的线性表有顺序表、链表、栈、队列等,本章将围绕顺序表和链表讲解。
顺序表一般指用一块连续的内存空间,依次存放数据。
由于顺序表要的空间是连续的,所以我们一般用数组的方式来存储数据,我们现在有以下两种结构。
静态开辟:
- #define Size 10//数据个数为10个
- typedef int SLDteType;//数据类型为int 以后更好改
- typedef struct SeqList
- {
- SLDateType a[Size];
- size_t size;
- }SeqList;
动态开辟:
- typedef int SLDateType;//数据类型为int
- typedef struct SeqList
- {
- SLDateType* a;//指向之后动态开辟空间的指针
- size_t size;//当前数据个数
- size_t capacity; //容量大小
- }SeqList;
静态顺序表的缺点是开辟空间后不能修改大小,可能导致开小了不够用或者是开大了浪费空间,在实际使用中也一般以动态顺序表为主。因此,下面我们将事件动态顺序表。
- void SeqListInit(SeqList* ps)
- {
- assert(ps != NULL);//防止对空指针的解引用
- ps->a = NULL;
- ps->capacity = 0;//我们默认容量为0,把默认容量放到判断是否需要扩容里
- ps->size = 0;
- }
结构体是我们自己在栈上创建的,所以不用用free释放,而结构体中a所指向的空间则是动态开辟的,在销毁表时应该free并且把其他成员置为0。
- void SeqListDestroy(SeqList* ps)
- {
- assert(ps != NULL);//防止对空指针的解引用
- free(ps->a);
- ps->a = NULL;//避免野指针
- ps->capacity = 0;
- ps->size = 0;
-
- }
扩容:在添加数据时,难免遇到空间不够的情况,针对此情况,我们先写一个函数,在增加数据时,先判断是否需要扩容,然后再插入数据。
- void SeqListChange(SeqList* ps)
- {
- if (ps->size == ps->capacity)
- {
- ps->capacity = ps->capacity == 0 ? 2 : 2 * ps->capacity;//如果容量大小为零,则改为2,否者改成原来大小的两倍
- SLDateType* newa = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * ps->capacity);
- if (newa == NULL)
- {
- perror("realloc:");
- exit(-1);
- }
- ps->a = newa;
- }
- }
增:在添加数据时,由于数据是连续存放的。除了在最后一个位置插入数据,在其他的位置插入数据都要把数据往后挪一个位置。
- void SeqListInsert(SeqList* ps, size_t pos, SLDateType x)
- {
- assert(ps);//防止对空指针解引用
- assert(pos >= 0);//防止在数组前插入数据导致越界
- assert(pos <= ps->size);//保证pos下标的合法性
- SeqListChange(ps);//判断是否需要扩容
- int i = ps->size;
- while (i > pos)//挪动数据
- {
- ps->a[i] = ps->a[i - 1];
- i--;
- }
- ps->a[i] = x;
- ps->size++;
- }
有了在任意位置插入数据的函数,头插和尾插也可以很方便的实现了。
- void SeqListPushFront(SeqList* ps, SLDateType x)//头插
- {
- assert(ps);
- SeqListInsert(ps, 0, x);
-
- }
-
- void SeqListPushBack(SeqList* ps, SLDateType x)//尾插
- {
- assert(ps);
- SeqListInsert(ps, ps->size, x);
-
- }
删:在删除数据时,我们要重点关注size是否为0,当size为0时则代表表已经被删空了,不能再删了。
- //删除任意位置的值
- void SeqListErase(SeqList* ps, size_t pos)
- {
- assert(ps);
- assert(pos < ps->size);//pos的值要在0到size-1之间
- assert(pos >= 0);
- int i = pos;
- while (i < ps->size - 1)//如果不是删除最后一个值的话,往前挪动位置
- {
- ps->a[i] = ps->a[i + 1];
- i++;
- }
- ps->size--;
- }
- //头删
- void SeqListPopFront(SeqList* ps)
- {
- assert(ps);
- SeqListErase(ps, 0);
- }
- //尾删
- void SeqListPopBack(SeqList* ps)/
- {
- assert(ps);
- SeqListErase(ps, ps->size-1);
- }

查:这个就非常简单了,挨个遍历,找到了就返回下标
-
- int SeqListFind(SeqList* ps, SLDateType x, int begin)
- {
- assert(ps);//防止空指针解引用
- int i = begin;//从begin下标的位置开始找
- while (i < ps->size)
- {
- if (ps->a[i] == x)
- {
- return i;
- }
- }
- return -1;
- }
链表在物理上不是连续的,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
链表可以分成单/双向、带/不带头、循/非循环,三种情况排列组合可以有8种情况,但是最常见的还是下面两种情况。
本章我们只实现单链表
- typedef int SLTDateType;
- typedef struct SListNode
- {
- SLTDateType data;//存储数据
- struct SListNode* next;//下一个节点的地址
- }SListNode;
-
- //创建一个结点
- SListNode* BuySListNode(SLTDateType* data)
- {
- SListNode* create = (SListNode*)malloc(sizeof(SListNode));
- if (!create)
- {
- perror("creat malloc file:");
- }
- create->data = data;//存放数据
- create->next = NULL;//将指针置为空避免野指针
- return create;//返回该节点的地址
- }

在销毁时需要注意,要先保存下一个节点的地址,否者的话cur就是野指针了,会找不到下一个节点造成对非动态内存的释放和内存泄露。
- void SListDestroy(SListNode** plist)
- {
- SListNode* cur = *plist;
- while (*plist)
- {
- cur = cur->next;//要先保存下一个的地址
- free(*plist);
- *plist = cur;
- }
- }
增:由于单链表只能找到下一个地址,所以一般是在下标的下一个位置添加。而且当要头插时,由于要改变指针,所以有时要参数为二级指针。
- // 单链表的头插
- void SListPushFront(SListNode** pplist, SLTDateType x)
- {
- SListNode* begin = BuySListNode(x);
- begin->next = *pplist;
- *pplist = begin;
- }
-
- // 单链表尾插
- void SListPushBack(SListNode** pplist, SLTDateType x)
- {
-
- SListNode* cur = *pplist;
- SListNode* newSLT = BuySListNode(x);
- if (*pplist==NULL)//当表为空时,要创建一个节点并返回该节点地址
- {
- *pplist = newSLT;
- }
- else
- {
- while (cur->next)
- {
- cur = cur->next;
- }
- cur->next = newSLT;
- }
- }
-
- // 单链表在pos位置之后插入x
- void SListInsertAfter(SListNode* pos, SLTDateType x)
- {
- assert(pos);
- SListNode* newnode = BuySListNode(x);
- newnode->next = pos->next;
- pos->next = newnode;
- }

删:由于在删除的过程中,当把最后一个节点删掉时,要把指针置为空避免野指针,形参的改变不会影响实参,所以我们可以用二级指针。
- // 单链表的尾删
- void SListPopBack(SListNode** pplist)
- {
- assert(*pplist);
- SListNode* cur = *pplist;
- SListNode* next = cur->next;
- if (next == NULL)
-
- {
- free(cur);
- *pplist = NULL;
- }
- else
- {
- while (next->next != NULL)
- {
- cur = next;
- next = next->next;
- }
- free(next);
- cur->next = NULL;
- }
- }
- // 单链表头删
- void SListPopFront(SListNode** pplist)
- {
- assert((*pplist));
- SListNode* next = (*pplist)->next;
- free((*pplist));
- if (next == NULL)
- {
- *pplist = NULL;
- }
- else
- {
- *pplist = next;
- }
- }
-
- //单链表删除pos位置的值
- void SListErase(SListNode** phead, SListNode* pos)
- {
- assert(pos);
- assert(phead);
-
- if (*phead == pos)
- {
- SListNode* next = (*phead)->next;
- free(*phead);
- *phead = next;
- }
- else
- {
- SListNode* cur = *phead;
- while (cur->next != pos)
- {
- cur = cur->next;
- }
- cur->next = cur->next->next;
- free(pos);
- }
- }

查:
- // 单链表查找
- SListNode* SListFind(SListNode* plist, SLTDateType x)
- {
- SListNode* cur = plist;
- while (cur != NULL)
- {
- if (cur->data == x)
- {
- return cur;
- }
- else
- {
- cur = cur->next;
- }
- }
- return cur;
- }

关于顺序表和链表的实现就到这里,现在介绍以下它们的不同点
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。