數據結構線性表（順序表，單鏈表）

線性表

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

由于這倆測試方法都差不多，所以只用了一個測試函數，這兩種數據結構都屬于線性結構，當然線性結構還有很多，之后會發表一些其他的線性表