行业资讯

数据结构线性表（顺序表，单链表）

发布时间：2020-05-28 10:34:14 作者：wx5d26a62f6f381
来源：网络 阅读：176

线性表

1.线性表的含义

       线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结 构，常见的线性表：顺序表、链表、栈、队列、字符串...线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物 理上存储时，通常以数组和链式结构的形式存储。

2.线性表图解

    

数据结构线性表（顺序表，单链表）

顺序表

数据结构线性表（顺序表，单链表）

单链表

4.代码实现

common.h

#ifndef _COMMON_H_
#define _COMMON_H_
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef enum{FALSE, TRUE} BOOL;
#define DataType int
#define DEFAULT_SIZE 8
#define INC_SIZE      3
void Swap(DataType *a, DataType *b)
{
 DataType tmp = *a;
 *a = *b;
 *b = tmp;
}
#endif /* _COMMON_H_ */

seqlist.h

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组 上完成数据的增删查改。

顺序表一般可以分为：
1）. 静态顺序表：使用定长数组存储。

2）. 动态顺序表：使用动态开辟的数组存储。

#ifndef _SEQLIST_H_
#define _SEQLIST_H_
#define NULL_DATA -1
typedef struct SeqList
{
 DataType *base;
 size_t    capacity;
 size_t    size;
}SeqList;
//内部方法
static BOOL _Inc(SeqList *psl);
BOOL SeqListIsFull(SeqList *psl);
BOOL SeqListIsEmpty(SeqList *psl);
void SeqListInit(SeqList* psl, size_t capacity);
void SeqListPushBack(SeqList* psl, DataType x);
void SeqListShow(SeqList *psl);
void SeqListPopBack(SeqList* psl);
void SeqListPopFront(SeqList* psl);
size_t SeqListLength(SeqList *psl);
void SeqListClear(SeqList *psl);
DataType SeqListFindByPos(SeqList *psl, int pos);
int SeqListFindByVal(SeqList *psl, DataType key);
BOOL SeqListEraseByVal(SeqList *psl, DataType key);
BOOL SeqListEraseByPos(SeqList *psl, int pos);
BOOL SeqListInsertByPos(SeqList *psl, int pos, DataType x);
void SeqListReverse(SeqList *psl);
void SeqListRemoveAll(SeqList* psl, DataType x);
void SeqListSort(SeqList *psl);
void SeqListDestroy(SeqList *psl);
BOOL _Inc(SeqList *psl)
{
 DataType *new_base = 
  (DataType *)malloc(sizeof(DataType)*(psl->capacity + INC_SIZE));
 if (new_base == NULL)
  return FALSE;
 
 memcpy(new_base, psl->base, sizeof(DataType)*psl->capacity);
 free(psl->base);
 psl->base = new_base;
 psl->capacity += INC_SIZE;
 return TRUE;
}
BOOL SeqListIsFull(SeqList *psl)
{
 if (psl->size >= psl->capacity)
  return TRUE;
 return FALSE;
}
BOOL SeqListIsEmpty(SeqList *psl)
{
 if (psl->size == 0)
  return TRUE;
 return FALSE;
}
////////////////////////////////////////////////////////////
void SeqListInit(SeqList* psl, size_t capacity)
{
 psl->base = (DataType*)malloc(sizeof(DataType)*capacity);
 assert(psl->base != NULL);
 psl->capacity = capacity;
 psl->size = 0;
}
void SeqListPushBack(SeqList* psl, DataType x)
{
 if (SeqListIsFull(psl) && !_Inc(psl))
 {
  printf("顺序表空间已满,%d不能插入.\n", x);
  return;
 }
 psl->base[psl->size++] = x;
}
void SeqListPushFront(SeqList* psl, DataType x)
{
 if (SeqListIsFull(psl) && !_Inc(psl))
 {
  printf("顺序表空间已满,%d不能插入.\n", x);
  return;
 }
 for (int i = psl->size; i > 0; --i)
 {
  psl->base[i] = psl->base[i - 1];
 }
 psl->base[0] = x;
 psl->size++;
}
void SeqListShow(SeqList *psl)
{
 for (int i = 0; i < psl->size; ++i)
 {
  printf("%d ", psl->base[i]);
 }
 printf("\n");
}
void SeqListPopBack(SeqList* psl)
{
 if (SeqListIsEmpty(psl))
 {
  printf("顺序表已空，不能删除.\n");
  return;
 }
 psl->size--;
}
void SeqListPopFront(SeqList* psl)
{
 if (SeqListIsEmpty(psl))
 {
  printf("顺序表已空，不能删除.\n");
  return;
 }
 for (int i = 0; i<psl->size-1; ++i)
 {
  psl->base[i] = psl->base[i + 1];
 }
 psl->size--;
}
size_t SeqListLength(SeqList *psl)
{
 return psl->size;
}
void SeqListClear(SeqList *psl)
{
 psl->size = 0;
}
DataType SeqListFindByPos(SeqList *psl, int pos)
{
 //assert(pos >= 0 && pos < psl->size);
 if (pos < 0 || pos >= psl->size)
 {
  printf("查询的位置无效.\n");
  return NULL_DATA;
 }
 return psl->base[pos];
}
int SeqListFindByVal(SeqList *psl, DataType key)
{
 for (int i = 0; i < psl->size; ++i)
 {
  if (key == psl->base[i])
   return i;
 }
 return -1;
}
BOOL SeqListEraseByPos(SeqList *psl, int pos)
{
 if (pos < 0 || pos >= psl->size)
  return FALSE;
 for (int i = pos; i < psl->size - 1; ++i)
  psl->base[i] = psl->base[i + 1];
 psl->size--;
 return TRUE;
}
BOOL SeqListEraseByVal(SeqList *psl, DataType key)
{
 int index = SeqListFindByVal(psl, key);
 if (index == -1)
  return FALSE;
 return SeqListEraseByPos(psl, index);
}
BOOL SeqListInsertByPos(SeqList *psl, int pos, DataType x)
{
 if (pos<0 || pos>psl->size)
  return FALSE;
 if (SeqListIsFull(psl) && !_Inc(psl))
 {
  printf("顺序表空间已满,%d不能插入.\n", x);
  return FALSE;
 }
 for (int i = psl->size; i > pos; --i)
  psl->base[i] = psl->base[i - 1];
 psl->base[pos] = x;
 psl->size++;
 return TRUE;
}
void SeqListReverse(SeqList *psl)
{
 if (psl->size >= 2)
 {
  int begin = 0;
  int end = psl->size - 1;
  while (begin < end)
  {
   Swap(&(psl->base[begin]), &(psl->base[end]));
   begin++;
   end--;
  }
 }
}
void SeqListRemoveAll(SeqList* psl, DataType x)
{
 for (int i = 0; i < psl->size; ++i)
 {
  if (x == psl->base[i])
  {
   for (int j = i; j < psl->size-1; ++j)
    psl->base[j] = psl->base[j + 1];
   psl->size--;
   i--;
  }
 }
}
void SeqListSort(SeqList *psl)
{
 for (int i = 0; i < psl->size - 1; ++i)
 {
  for (int j = 0; j < psl->size - i - 1; ++j)
  {
   if (psl->base[j] > psl->base[j + 1])
   {
    Swap(&(psl->base[j]), &(psl->base[j + 1]));
   }
  }
 }
}
void SeqListDestroy(SeqList *psl)
{
 free(psl->base);
 psl->base = NULL;
 psl->capacity = psl->size = 0;
}

slist.h

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链 接次序实现的

#ifndef _SLIST_H_
#define _SLIST_H_
#include"common.h"
typedef struct SListNode
{
 DataType data;
 struct SListNode *next; //link
}SListNode;
typedef struct SList
{
 SListNode *first;
 SListNode *last;
 size_t     size;
}SList;

SListNode* _Buynode(DataType x)
{
 SListNode *s = (SListNode *)malloc(sizeof(SListNode));
 assert(s != NULL);
 s->data = x;
 s->next = NULL;
 return s;
}
void SListInit(SList* plist);
void SListPushBack(SList *plist, DataType x);
void SListPushFront(SList *plist, DataType x);
void SListShow(SList *plist);
SListNode* SListFindByVal(SList *plist, DataType key);
BOOL SListEraseByVal(SList *plist, DataType key);
void SListInit(SList* plist)
{
 SListNode *s = _Buynode(0);
 plist->first = plist->last = s;
 plist->size = 0;
}
void SListPushBack(SList *plist, DataType x)
{
 assert(plist != NULL);
 SListNode *s = _Buynode(x);
 plist->last->next = s;
 plist->last = s;
 plist->size++;
}
void SListPushFront(SList *plist, DataType x)
{
 assert(plist != NULL);
 SListNode *s = _Buynode(x);
 s->next = plist->first->next;
 plist->first->next = s;
 //判断是否插入的是第一个节点
 if (plist->size == 0)
  plist->last = s;
 plist->size++;
}
void SListShow(SList *plist)
{
 SListNode *p = plist->first->next;
 while (p != NULL)
 {
  printf("%d-->", p->data);
  p = p->next;
 }
 printf("Over.\n");
}
SListNode* SListFindByVal(SList *plist, DataType key)
{
 assert(plist != NULL);
 SListNode *p = plist->first->next;
 while (p != NULL && p->data != key)
  p = p->next;
 return p;
}
BOOL SListEraseByVal(SList *plist, DataType key)
{
 assert(plist != NULL);
 SListNode *p, *q;
 p = SListFindByVal(plist, key);
 if(p == NULL)
  return FALSE;
 q = p->next;
 if (q == plist->last)
  plist->last = p;
 p->data = q->data;
 p->next = q->next;
 free(q);
 plist->size--;
 return TRUE;
}
#if 0
typedef SListNode *List;
//////////////////////////////////////////////////
void SListInit(List *head);
void SListCreate_Back(List *head);
void SListCreate_Front(List *head);
void SListCreate_Back1(List *head);
void SListShow(List head);
SListNode* _Buynode(DataType x)
{
 SListNode *s = (SListNode *)malloc(sizeof(SListNode));
 assert(s != NULL);
 s->data = x;
 s->next = NULL;
 return s;
}
void SListInit(List *head)
{
 *head = _Buynode(0);
}
void SListCreate_Back(List *head)
{
 SListNode *p = *head;
 for(int i=1; i<=10; ++i)
 {
  SListNode *s = _Buynode(i);
  p->next = s;
  p = s;
 }
}
void SListCreate_Front(List *head)
{
 for (int i = 1; i <= 10; ++i)
 {
  SListNode *s = _Buynode(i);
  s->next = (*head)->next;
  (*head)->next = s;
 }
}
void SListShow(List head)
{
 SListNode *p = head->next;
 while (p != NULL)
 {
  printf("%d-->", p->data);
  p = p->next;
 }
 printf("Over.\n");
}
void SListInit(List *head)
{
 *head = NULL;
}
void SListCreate_Back(List *head)
{
 *head = (SListNode*)malloc(sizeof(SListNode));
 assert(*head != NULL);
 (*head)->data = 1;
 (*head)->next = NULL;
 SListNode *p = *head;
 for (int i = 2; i <= 10; ++i)
 {
  SListNode *s = (SListNode*)malloc(sizeof(SListNode));
  assert(s != NULL);
  s->data = i;
  s->next = NULL;
  p->next = s;
  p = s;
 }
}
void SListCreate_Front(List *head)
{
 //1 创建第一个节点
 *head = (SListNode*)malloc(sizeof(SListNode));
 assert(*head != NULL);
 (*head)->data = 1;
 (*head)->next = NULL;
 //2 循环创建节点进行头插
 for (int i = 2; i <= 10; ++i)
 {
  SListNode *s = (SListNode*)malloc(sizeof(SListNode));
  assert(s != NULL);
  s->data = i;
  s->next = *head;
  *head = s;
 }
}
void SListCreate_Back1(List *head)
{
 *head = (SListNode*)malloc(sizeof(SListNode));
 assert(*head != NULL);
 (*head)->data = 1;
 (*head)->next = NULL;
 SListNode *p = *head;
 for (int i = 2; i <= 10; ++i)
 {
  p = p->next = (SListNode*)malloc(sizeof(SListNode));
  assert(p != NULL);
  p->data = i;
  p->next = NULL;
 }
}
void SListShow(List head)
{
 SListNode *p = head;
 while (p != NULL)
 {
  printf("%d-->", p->data);
  p = p->next;
 }
 printf("Over.\n");
}
#endif

test.c

#include"common.h"
#include"seqlist.h"
#include"slist.h"
int main(int argc, char *argv[])
{
 //SeqList mylist;
 SListNode *p = NULL;
 SList mylist;
 SListInit(&mylist);
 DataType item;
 int pos, index;
 BOOL flag;
 int select = 1;
 while (select)
 {
  printf("************************************\n");
  printf("* [1] push_back     [2] push_front *\n");
  printf("* [3] show_list     [0] quit_system*\n");
  printf("* [4] pop_back      [5] pop_front  *\n");
  printf("* [6] find_pos      [7] find_val   *\n");
  printf("* [8] insert_pos    [9] delete_val *\n");
  printf("* [10] delete_pos   [11]length     *\n");
  printf("* [12] remove_all   [13] reverse   *\n");
  printf("* [14] sort         [15] clear     *\n");
  printf("************************************\n");
  printf("请选择:>");
  scanf("%d", &select);
  if (select == 0)
   break;
  switch (select)
  {
  case 1:
   printf("请输入要插入的数据(以-1结束):>");
   while (scanf("%d", &item), item != -1)
   {
    SListPushBack(&mylist, item);
   }
   break;
  case 2:
   printf("请输入要插入的数据(以-1结束):>");
   while (scanf("%d", &item), item != -1)
   {
    SListPushFront(&mylist, item);
   }
   break;
  case 3:
   SListShow(&mylist);
   break;
  case 4:
   //SeqListPopBack(&mylist);
   break;
  case 5:
   //SeqListPopFront(&mylist);
   break;
  case 6:
   printf("请输入要查询的位置:>");
   scanf("%d", &pos);
   //printf("要查询的数据:%d\n", SeqListFindByPos(&mylist, pos));
   break;
  case 7:
   printf("请输入要查询的数据:>");
   scanf("%d", &item);
   //index = SeqListFindByVal(&mylist, item);
   p = SListFindByVal(&mylist, item);
   if (p==NULL)
    printf("要查询的数据%d不存在.\n", item);
   break;
  case 8:
   printf("请输入要插入的位置:>");
   scanf("%d", &pos);
   printf("请输入要插入的数据:>");
   scanf("%d", &item);
   //flag = SeqListInsertByPos(&mylist, pos, item);
   if (flag)
    printf("插入成功.\n");
   else
    printf("插入失败.\n");
   break;
  case 9:
   printf("请输入要删除的数据:>");
   scanf("%d", &item);
   //flag = SeqListEraseByVal(&mylist, item);
   SListEraseByVal(&mylist, item);
   break;
  case 10:
   printf("请输入要删除的位置:>");
   scanf("%d", &pos);
   //flag = SeqListEraseByPos(&mylist, pos);
   if (flag)
    printf("删除成功.\n");
   else
    printf("删除失败.\n");
   break;
  case 11:
   printf("SeqList Length = %d\n", SeqListLength(&mylist));
   break;
  case 12:
   printf("请输入要删除的数据:>");
   scanf("%d", &item);
   //SeqListRemoveAll(&mylist, item);
   break;
  case 13:
   //SeqListReverse(&mylist);
   break;
  case 14:
   //SeqListSort(&mylist);
   break;
  case 15:
   //SeqListClear(&mylist);
   break;
  }
 }
 //SeqListDestroy(&mylist);
 return 0; 
}

由于这俩测试方法都差不多，所以只用了一个测试函数，这两种数据结构都属于线性结构，当然线性结构还有很多，之后会发表一些其他的线性表



推荐阅读：
  1. 【C语言数据结构】静态单链表
  2. 【C语言数据结构】单链表

免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。

线性表单链表顺序表

上一篇：什么是控制帧和数据帧？

下一篇：hadoop namenod的管理机制和存储细节

相关阅读

您好，登录后才能下订单哦！

密码登录
登录注册
获取短信验证码
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》
产品服务
地区划分
帮助支持
关于我们
行业资讯-文章归档 问答-问答归档
广州亿速云计算有限公司

7*24小时在线电话：400-100-2938

7*24小时在线QQ：800811969

Copyright © Yisu Cloud Ltd. All Rights Reserved. 2018 版权所有
粤ICP备17096448号-1 粤公网安备 44010402001142号