专业的公司网站建设/市场营销策略

相关概念

线性表的顺序存储结构，除了上一篇博客所讲的静态数组表示法以外，还有一种动态数组表示法。就是在执行诸如初始化线性表、销毁线性表、插入元素等动作的时候，会动态的分配内存空间，来合理的申请和释放内存资源。具体地说，C/C++ 语言中有 malloc/free、new/delete 函数来支持这种操作。

线性表动态数组表示法的定义

这里只须注意元素位序和数组下标的关系：i = j+1

/* 线性表的动态数组表示法 -- 定义 */

#ifndef DLISTOPERATION_H_INCLUDED

#define DLISTOPERATION_H_INCLUDED

#define MAX_NUM 200

typedef struct{

int *A;

int listsize;

int listlength;

}DLIST;

bool InitList(DLIST &L);

void DestroyList(DLIST &L);

void ClearList(DLIST &L);

bool ListEmpty(DLIST L);

int ListLength(DLIST L);

int GetElem(DLIST L, int i, int &e);

int LocateElem(DLIST L, int e);

bool PriorElem(DLIST L, int cur_e, int &pre_e);

bool NextElem(DLIST L, int cur_e, int &next_e);

int ListInsert(DLIST &L, int i, int e);

int ListDelete(DLIST &L, int i, int &e);

void ListTravers(DLIST L);

void Merge(DLIST &L1, DLIST &L2);

void minus(DLIST &L1, DLIST &L2);

#endif // DLISTOPERATION_H_INCLUDED

线性表动态数组表示法的12种基本操作

这里我采用了 malloc()、free()、realloc() 函数来实现动态数组，不多说，上代码：

/* 线性表的动态数组表示法 -- 12种基本操作 */

#include

#include

#include "DlistOperation.h"

bool InitList(DLIST &L){ //创建一个空线性表

L.A = (int*)malloc(sizeof(int)*MAX_NUM);//给A指针动态分配MAX_NUM长度的数组,Elemtype

if (L.A == NULL) return false;

L.listsize = MAX_NUM;

L.listlength = 0;

return true;

}

void DestroyList(DLIST &L){ //销毁线性表

free(L.A);

L.listsize = 0;

L.listlength = 0;

}

void ClearList(DLIST &L){ //线性表重置空

L.listlength = 0;

}

bool ListEmpty(DLIST L){ //判断线性表是否为空

if (L.listlength == 0) return true;

else return false;

}

int ListLength(DLIST L){ //返回线性表长度

return L.listlength;

}

int GetElem(DLIST L, int i, int &e){ //获取线性表位序为i的元素

//合法性校验

if (i < 1) return -1;

if (i > L.listlength) return -2;

e = L.A[i-1]; return 0;

}

int LocateElem(DLIST L, int e){ //返回线性表首个e元素的位序

for (int i = 0; i < L.listlength; i++){

if (L.A[i] == e)

return i+1;

}

return 0;

}

bool PriorElem(DLIST L, int cur_e, int &pre_e){ //获取cur_e元素的直接前驱

if (cur_e == L.A[0]) return false;

for (int i = 1; i < L.listlength; i++){

if (cur_e == L.A[i]){

pre_e = L.A[i-1];

return true;

}

}

return false;

}

bool NextElem(DLIST L, int cur_e, int &next_e){ //获取cur_e元素的直接后继

if (cur_e == L.A[L.listlength-1]) return false;

for (int i=0; i < L.listlength-1; i++){

if(cur_e == L.A[i]){

next_e = L.A[i+1];

return true;

}

}

return false;

}

int ListInsert(DLIST &L, int i, int e){ //在顺序表位序为i的元素前面插入元素e

//合法性校验

if (i<1) return -1;

if (i>L.listlength+1) return -2;

if (L.listlength == L.listsize){

L.A = (int*)realloc(L.A, sizeof(int)*(MAX_NUM+1));

if (L.A == NULL)

return -3;

}

for (int j = L.listlength; j >= i; j--){

L.A[j] = L.A[j-1];

}

L.A[i-1] = e;

L.listlength++;

return 0;

}

int ListDelete(DLIST &L, int i, int &e){ //删除顺序表位序为i的元素

//合法性校验

if (i<1) return -1;

if (i>L.listlength) return -2;

e = L.A[i-1];

for (int j = i; j <= L.listlength-1; j++){

L.A[j-1] = L.A[j];

}

L.listlength--;

return 0;

}

void ListTravers(DLIST L){ //遍历顺序表

for (int i = 0; i < L.listlength; i++){

printf("%d ",L.A[i]);

}

printf("\n");

}

void Merge(DLIST &L1, DLIST &L2){

int tp;

while (!ListEmpty(L2)){

ListDelete(L2,1,tp);

if (!LocateElem(L1,tp))

ListInsert(L1,L1.listlength+1,tp);

}

DestroyList(L2);

}

void minus(DLIST &L1, DLIST &L2){

int temp,pos;

while (!ListEmpty(L2)){

ListDelete(L2,1,temp);

if ((pos = LocateElem(L1,temp)) != 0){

ListDelete(L1,pos,temp);

}

}

DestroyList(L2);

}

线性表动态数组表示法的应用 完整的基本操作函数调用，如下示例：

/* 线性表的动态数组表示法 -- 应用 */

#include

#include

#include

#include "DlistOperation.h"

int main(){

int temp,select,item;

char str[30],*th,ch;

DLIST La,Lb;

InitList(La);

InitList(Lb);

printf("请给 La 顺序表赋值 ：\n");

gets(str);

th = strtok(str," ");

while(th != NULL){

temp = atoi(th);

ListInsert(La,La.listlength+1,temp);

th = strtok(NULL," ");

}

printf("\n");

printf("1: 创建一个空线性表 \n");

printf("2: 销毁线性表 \n");

printf("3: 线性表重置空 \n");

printf("4: 判断线性表是否为空 \n");

printf("5: 返回线性表长度 \n");

printf("6: 获取线性表位序为i的元素 \n");

printf("7: 返回线性表首个e元素的位序 \n");

printf("8: 获取cur_e元素的直接前驱 \n");

printf("9: 获取cur_e元素的直接后继 \n");

printf("10: 在顺序表位序为i的元素前面插入元素e \n");

printf("11: 删除顺序表位序为i的元素 \n");

printf("12: 依次输出顺序表的所有元素 \n");

printf("13: A并B \n");

printf("14: A - B \n");

printf("请选择 (1---14) \n\n");

scanf("%d",&select);

switch(select){

case 1:

DLIST Lt;

if (InitList(Lt))

printf("已创建顺序表Lt!\n");

else

printf("创建失败！\n");

break;

case 2:

printf("确定要删除顺序表La? \n");

ch = getchar();

if (ch == 'y' || ch == 'Y'){

DestroyList(La);

printf("已销毁顺序表La!\n");

}

else

printf("非法输入!\n");

break;

case 3:

ClearList(La);

printf("顺序表La已置空！\n");

break;

case 4:

if (ListEmpty(La))

printf("顺序表La是空的！\n");

else

printf("顺序表La非空！\n");

break;

case 5:

printf("顺序表La的长度是 %d\n",ListLength(La));

break;

case 6:

printf("请输入你想获取第几位数据？\n");

scanf("%d",&temp);

if (!(GetElem(La,temp,item)))

printf("第%d位元素是：%d\n",temp,item);

else

printf("非法位序！\n");

break;

case 7:

printf("请输入你想要查找的元素: ");

scanf("%d",&temp);

if ((item = LocateElem(La,temp)) == 0)

printf("你所查找的元素不存在！\n");

else

printf("%d元素首次出现在第%d位上！\n",temp,item);

break;

case 8:

printf("你想获得哪个元素值的前驱？\n");

scanf("%d",&temp);

if(PriorElem(La,temp,item))

printf("首次出现的%d元素的直接前驱是 %d\n",temp,item);

else

printf("输入非法！\n");

break;

case 9:

printf("你想获得哪个元素的后继？\n");

scanf("%d",&temp);

if(NextElem(La,temp,item))

printf("首次出现的%d元素的直接后继是 %d\n",temp,item);

else

printf("输入非法！\n");

break;

case 10:

printf("您想在第几个元素前面插入新元素？<1-%d>\n",ListLength(La)+1);

scanf("%d",&temp);

printf("您想插入的新元素是：");

scanf("%d",&item);

if(!ListInsert(La,temp,item)){

printf("插入成功！\n");

printf("新顺序表为：");

ListTravers(La);

}

else

printf("输入错误！\n");

break;

case 11:

printf("请输入您想删除的位序：");

scanf("%d",&temp);

if(!ListDelete(La,temp,item)){

printf("元素 %d 删除成功！\n",item);

printf("删除后的顺序表为：");

ListTravers(La);

}

else

printf("非法输入！\n");

break;

case 12:

printf("你输入的顺序表为：");

ListTravers(La);

break;

case 13:

getchar();

printf("请给 Lb 顺序表赋值 ：\n");

gets(str);

th = strtok(str," ");

while(th != NULL){

temp = atoi(th);

ListInsert(Lb,Lb.listlength+1,temp);

th = strtok(NULL," ");

}

Merge(La,Lb);

printf("合并后的 La 为：");

ListTravers(La);

break;

case 14:

getchar();

printf("请给 Lb 顺序表赋值 ：\n");

gets(str);

th = strtok(str," ");

while(th != NULL){

temp = atoi(th);

ListInsert(Lb,Lb.listlength+1,temp);

th = strtok(NULL," ");

}

minus(La,Lb);

printf("相减后的 La 为：");

ListTravers(La);

break;

}

return 0;

}

程序运行结果，如下图示例：

好啦，这部分内容就这些，很简单。后面一篇博客，我会利用线性表的顺序存储结构来实现一个Joseph环，小试牛刀，感兴趣的可以看看~有问题请联系我：lichucnhun4.0@gmail.com

转载请声明出处：http://blog.csdn.net/zhongkelee