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

线性表

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; 
}

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