真实的国产乱ⅩXXX66竹夫人,五月香六月婷婷激情综合,亚洲日本VA一区二区三区,亚洲精品一区二区三区麻豆

成都創(chuàng)新互聯(lián)網(wǎng)站制作重慶分公司

數(shù)據(jù)結(jié)構(gòu)線性表（順序表，單鏈表）

線性表

創(chuàng)新互聯(lián)建站提供成都網(wǎng)站建設(shè)、網(wǎng)站設(shè)計(jì)、網(wǎng)頁(yè)設(shè)計(jì)，品牌網(wǎng)站制作，廣告投放等致力于企業(yè)網(wǎng)站建設(shè)與公司網(wǎng)站制作，10余年的網(wǎng)站開發(fā)和建站經(jīng)驗(yàn),助力企業(yè)信息化建設(shè)，成功案例突破上千家,是您實(shí)現(xiàn)網(wǎng)站建設(shè)的好選擇.

1.線性表的含義

? ? ?? 線性表（linear list）是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。 線性表是一種在實(shí)際中廣泛使用的數(shù)據(jù)結(jié) 構(gòu)，常見的線性表：順序表、鏈表、棧、隊(duì)列、字符串...線性表在邏輯上是線性結(jié)構(gòu)，也就說(shuō)是連續(xù)的一條直線。但是在物理結(jié)構(gòu)上并不一定是連續(xù)的，線性表在物 理上存儲(chǔ)時(shí)，通常以數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu)的形式存儲(chǔ)。

2.線性表圖解

? ??

數(shù)據(jù)結(jié)構(gòu)線性表（順序表，單鏈表）

順序表

數(shù)據(jù)結(jié)構(gòu)線性表（順序表，單鏈表）

單鏈表

4.代碼實(shí)現(xiàn)

common.h

#ifndef?_COMMON_H_
#define?_COMMON_H_
#include
#include
#include
#include
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

順序表是用一段物理地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲(chǔ)。在數(shù)組 上完成數(shù)據(jù)的增刪查改。

順序表一般可以分為：
1）. 靜態(tài)順序表：使用定長(zhǎng)數(shù)組存儲(chǔ)。

2）. 動(dòng)態(tài)順序表：使用動(dòng)態(tài)開辟的數(shù)組存儲(chǔ)。

#ifndef?_SEQLIST_H_
#define?_SEQLIST_H_
#define?NULL_DATA?-1
typedef?struct?SeqList
{
?DataType?*base;
?size_t????capacity;
?size_t????size;
}SeqList;
//內(nèi)部方法
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?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;?isize-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?size);
?if?(pos?=?psl->size)
?{
??printf("查詢的位置無(wú)效.\n");
??return?NULL_DATA;
?}
?return?psl->base[pos];
}
int?SeqListFindByVal(SeqList?*psl,?DataType?key)
{
?for?(int?i?=?0;?i?size;?++i)
?{
??if?(key?==?psl->base[i])
???return?i;
?}
?return?-1;
}
BOOL?SeqListEraseByPos(SeqList?*psl,?int?pos)
{
?if?(pos?=?psl->size)
??return?FALSE;
?for?(int?i?=?pos;?i?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?base[begin]),?&(psl->base[end]));
???begin++;
???end--;
??}
?}
}
void?SeqListRemoveAll(SeqList*?psl,?DataType?x)
{
?for?(int?i?=?0;?i?size;?++i)
?{
??if?(x?==?psl->base[i])
??{
???for?(int?j?=?i;?j?size-1;?++j)
????psl->base[j]?=?psl->base[j?+?1];
???psl->size--;
???i--;
??}
?}
}
void?SeqListSort(SeqList?*psl)
{
?for?(int?i?=?0;?i?size?-?1;?++i)
?{
??for?(int?j?=?0;?j?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

鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈 接次序?qū)崿F(xiàn)的

#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;
?//判斷是否插入的是第一個(gè)節(jié)點(diǎn)
?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?創(chuàng)建第一個(gè)節(jié)點(diǎn)
?*head?=?(SListNode*)malloc(sizeof(SListNode));
?assert(*head?!=?NULL);
?(*head)->data?=?1;
?(*head)->next?=?NULL;
?//2?循環(huán)創(chuàng)建節(jié)點(diǎn)進(jìn)行頭插
?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("請(qǐng)選擇:>");
??scanf("%d",?&select);
??if?(select?==?0)
???break;
??switch?(select)
??{
??case?1:
???printf("請(qǐng)輸入要插入的數(shù)據(jù)(以-1結(jié)束):>");
???while?(scanf("%d",?&item),?item?!=?-1)
???{
????SListPushBack(&mylist,?item);
???}
???break;
??case?2:
???printf("請(qǐng)輸入要插入的數(shù)據(jù)(以-1結(jié)束):>");
???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("請(qǐng)輸入要查詢的位置:>");
???scanf("%d",?&pos);
???//printf("要查詢的數(shù)據(jù):%d\n",?SeqListFindByPos(&mylist,?pos));
???break;
??case?7:
???printf("請(qǐng)輸入要查詢的數(shù)據(jù):>");
???scanf("%d",?&item);
???//index?=?SeqListFindByVal(&mylist,?item);
???p?=?SListFindByVal(&mylist,?item);
???if?(p==NULL)
????printf("要查詢的數(shù)據(jù)%d不存在.\n",?item);
???break;
??case?8:
???printf("請(qǐng)輸入要插入的位置:>");
???scanf("%d",?&pos);
???printf("請(qǐng)輸入要插入的數(shù)據(jù):>");
???scanf("%d",?&item);
???//flag?=?SeqListInsertByPos(&mylist,?pos,?item);
???if?(flag)
????printf("插入成功.\n");
???else
????printf("插入失敗.\n");
???break;
??case?9:
???printf("請(qǐng)輸入要?jiǎng)h除的數(shù)據(jù):>");
???scanf("%d",?&item);
???//flag?=?SeqListEraseByVal(&mylist,?item);
???SListEraseByVal(&mylist,?item);
???break;
??case?10:
???printf("請(qǐng)輸入要?jiǎng)h除的位置:>");
???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("請(qǐng)輸入要?jiǎng)h除的數(shù)據(jù):>");
???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;?
}

由于這倆測(cè)試方法都差不多，所以只用了一個(gè)測(cè)試函數(shù)，這兩種數(shù)據(jù)結(jié)構(gòu)都屬于線性結(jié)構(gòu)，當(dāng)然線性結(jié)構(gòu)還有很多，之后會(huì)發(fā)表一些其他的線性表


名稱欄目：數(shù)據(jù)結(jié)構(gòu)線性表（順序表，單鏈表）
轉(zhuǎn)載源于：http://weahome.cn/article/ipdjoj.html

其他資訊

在線咨詢

微信咨詢

電話咨詢

028-86922220（工作日）

18980820575（7×24）

提交需求

返回頂部