现在的位置: 首页 > 自动控制 > 工业·编程 > 正文

数据结构-线性表

2019-04-07 21:20 工业·编程 ⁄ 共 8142字 ⁄ 字号 暂无评论

1. 线性表:n个数据元素的有序集合。

线性表是一种常用的数据结构。在实际应用中,线性表都是以栈、队列、字符串、数组等特殊线性表的形式来使用的。由于这些特殊线性表都具有各自的特性,因此,掌握这些特殊线性表的特性,对于数据运算的可靠性和提高操作效率都是至关重要的。 线性表是一个线性结构,它是一个含有n≥0个结点的有限序列,对于其中的结点,有且仅有一个开始结点没有前驱但有一个后继结点,有且仅有一个终端结点没有后继但有一个前驱结点,其它的结点都有且仅有一个前驱和一个后继结点。

特征

1.集合中必存在唯一的一个“第一元素”;

2.集合中必存在唯一的一个 “最后元素” ;

3.除最后一个元素之外,均有 唯一的后继(后件);

4.除第一个元素之外,均有 唯一的前驱(前件)。

java中的List接口,就是线性表。ArrayList就是顺序线性表,LinkedList就是链表线性表。

2. 线性表的顺序表示:ArrayList

一般使用数组(C语言中的数组采用顺序存储方式。即连续地址存储)来描述。

优点:在于随机访问元素,

缺点:插入和和删除的时候,需要移动大量的元素。

c语言实现代码

// Test.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

#include <stdio.h>

#include "stdlib.h"

//宏定义

#define TRUE   1

#define FALSE   0

#define OK    1

#define ERROR   0

#define INFEASIBLE -1

#define OVERFLOW -2

#define LT(a,b)   ((a)<(b))

#define N = 100      

#define LIST_INIT_SIZE 100 //线性表初始空间分配量

#define LISTINCREMENT   10 //线性表空间分配的增量

typedef int Status;

typedef int ElemType;

typedef struct LNode{

ElemType  *elem;        //存储空间的基地址

int      lenght; //当前的长度

int  listsize;      //当前分配的存储容量

}SqList;

/**

*构造空的线性表

*/

Status initList(SqList &L, int lenght){

if (lenght == 0) lenght = LIST_INIT_SIZE;

L.elem = (ElemType *)malloc(lenght * sizeof(ElemType));

if(!L.elem) exit(OVERFLOW);  //分配存储空间失败

L.lenght = 0;  //初始空表长度为0

L.listsize = lenght ;//初始存储容量为100

return OK;

}

/************************************************************************/

/* 在第i位置插入e

*/

/************************************************************************/

Status insertList(SqList &L, ElemType e, int i){

ElemType *p,  *q;

if(i<0 ||i > L.lenght) return ERROR;  //i值不合法

if (L.lenght >= L.listsize) {

ElemType *newbase = (ElemType *)realloc(L.elem ,(L.listsize +LISTINCREMENT)*sizeof(ElemType));

if(!newbase) return OVERFLOW; //存储分配失败 

L.elem = newbase; //新基值

L.listsize += LISTINCREMENT;    //增加存储容量

}

q = &L.elem[i]; //q为插入的位置

for (p = &L.elem[L.lenght]; p>=q; --p) {

*p = *(p-1); //i元素之后的元素往后移动

}

*q = e; //插入e

L.lenght +=1;

return OK;

}

/************************************************************************/

/* 快速排序

*/

/************************************************************************/

void sortList(SqList &L){

}

/************************************************************************/

/* 删除第i位置元素,并用e返回其值                                                                     */

/************************************************************************/

Status deleteListElem(SqList &L, int i, ElemType &e){

int *p,  *q;

if(i<0 ||i > L.lenght) return ERROR;  //i值不合法

q = &L.elem[i];   //被删除元素的位置为i,L.elem就是数组名,

e = *q;   //被删除元素的值赋值给e

for (p = q; p< (L.elem + L.lenght); p++){ //元素左移

*p = *(p+1);

}

--L.lenght;

return OK;

}

/************************************************************************/

/*  快速排序

*/

/************************************************************************/

int partition(SqList &L, ElemType low, ElemType high){

ElemType pivotkey = L.elem[low];        //枢轴记录关键字

while (low < high) {  //从表的两端向中间扫描

while (low < high &&  L.elem[high] >= pivotkey ) --high;//高端位置扫描

L.elem[low] = L.elem[high]; //交换数据,小于pivotkey移到低端

L.elem[high] = pivotkey;

while (low < high && L.elem[low] <= pivotkey ) ++low;     //低端扫描

L.elem[high] = L.elem[low];   //交换数据 大于pivotkey移到高端

L.elem[low] = pivotkey;

}

return low;

}

void quickSort(SqList &L, ElemType low, ElemType high){

int pivot;

if(low < high) {

pivot =  partition(L,  low,  high);

quickSort(L,  low,  pivot -1); //低端子表排序

quickSort(L,  pivot +1, high); //高端子表排序

}

}

/************************************************************************/

/*

合并两个线性表

*/

/************************************************************************/

void mergeList(SqList La, SqList Lb,  SqList &Lc){

ElemType *pa, *pb, *pc;

Lc.listsize =  La.lenght + Lb.lenght;

initList(Lc, Lc.listsize); //初始化LC\pc = Lc.elem;

Lc.lenght = Lc.listsize;

pc = Lc.elem;

pa = La.elem;

pb = Lb.elem;

while (pa <= &La.elem[La.lenght -1] && pb <= &Lb.elem[Lb.lenght -1]){

if (*pa <= *pb) *pc++ = *pa++;

else *pc++ = *pb++;

}

while(pa <= &La.elem[La.lenght -1]) *pc++ = *pa++; //插入La的剩余元素

while(pb <= &Lb.elem[Lb.lenght -1]) *pc++ = *pb++; //插入Lb的剩余元素

}

/************************************************************************/

/* 打印list

*/

/************************************************************************/

void printList(SqList L){

printf("当前值:");

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

printf("%d ", *(L.elem+i)); // L.elem为首地址

}

printf("\r\n");

}

void main()

{

SqList La,Lb,Lc;

ElemType e;

int init,i;

init = initList(La, LIST_INIT_SIZE);

int data[6] = {5,3,6,2,7,4};

for (i=0; i<6;i++) {

insertList(La,  data[i],  i);

}

printf("LA:\r\n");

printList(La);

deleteListElem(La, 3, e );

printList(La);

insertList(La,  e,  3);

printList(La);

//排序

quickSort(La,0, La.lenght-1);

printList(La);

printf("LB:\r\n");

initList(Lb, LIST_INIT_SIZE);

int Bdata[5] = {1,3,2,4,6};

for (i=0; i<5;i++) {

insertList(Lb,  Bdata[i],  i);

}

//排序

quickSort(Lb,0, Lb.lenght-1);

printList(Lb);

mergeList(La, Lb,  Lc);

printList(Lc);

}

3. 线性表的链表表示LinkedList

一般使用链表来描述。

优点:对于新增和删除操作add和remove和方便。不需要移动元素。

缺点:不方便随机访问元素,LinkedList要移动指针

代码实现

// Test.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

#include <stdio.h>

#include "stdlib.h"

//宏定义

#define TRUE   1

#define FALSE   0

#define OK    1

#define ERROR   0

#define INFEASIBLE -1

#define OVERFLOW -2

#define LT(a,b)   ((a)<(b))

#define N = 100      

typedef int Status;

typedef int ElemType;

typedef struct LNode{

ElemType  data;

struct LNode   *next;

}LNode, *LinkList;

/************************************************************************/

/*

初始化链表

*/

/************************************************************************/

Status initList(LinkList &L){

/*单链表的初始化*/

L = (LinkList)malloc(sizeof(LNode));    //申请一个头节点

if(!L) exit(OVERFLOW); //申请空间失败 

L->next=NULL; //建立一个带都节点的空链表

return OK;

/*

需要改变指针的指针,所以参数必须是引用或者是 *L:

(*L) = (Lnode *)malloc(sizeof(Lnode));

(*L)->next=NULL;

return 1;                                                                    

*/

}

/************************************************************************/

/*    

创建链表

*/

/************************************************************************/

void createList(LinkList L, int n){

/*单链表的初始化*/

if (!L) {

initList(L);

}

ElemType data;

LinkList p,q = L;

printf("输入节点数据的个数%d:\r\n", n);

for(int i = 0; i<n; i++) {

p = (LinkList) malloc( sizeof(LNode)); //申请一个新节点

scanf("%d",&data);

p->data = data;

p->next = q->next;

q->next = p;

q = p;

}

}

/************************************************************************/

/* 在第i位置插入e

*/

/************************************************************************/

Status insertList(LinkList L, ElemType e, int i){

LinkList s, p = L;

int j = 0;

while (p && j<i){ //寻找i节点

p = p->next;

j++;

}

if (!p ||j >i) return ERROR;

s = (LinkList) malloc(sizeof(LNode)); //生成新节点

s->data = e; s->next = p->next; //插入L中

p->next = s;

return OK;

}

/************************************************************************/

/* 删除第i位置元素,并用e返回其值                                                                     */

/************************************************************************/

Status deleteListElem(LinkList L, int i, ElemType &e){

LinkList p, q;

int j = 0;

p = L;

while (p && j<i){

p = p->next;

++j;

}

if (!p->next || j>i)  return ERROR;   //删除的位置不对

q  = p->next; p->next = q->next;

e = q->data; free(q); //释放节点

return OK;

}

/************************************************************************/ 

/*  插入排序

*/ 

/************************************************************************/ 

void  InsertSort(LinkList L)

{

LinkList  list; /*为原链表剩下用于直接插入排序的节点头指针*/

LinkList  node; /*插入节点*/

LinkList  p;

LinkList  q;

list = L->next; /*原链表剩下用于直接插入排序的节点链表*/

L->next = NULL; /*只含有一个节点的链表的有序链表。*/

while (list != NULL)   { /*遍历剩下无序的链表*/

node = list, q = L;  

while (q && node->data > q->data  ) {

p = q;

q = q->next;

}

if (q == L) {  /*插在第一个节点之前*/

L = node;

}  else {   /*p是q的前驱*/

p->next = node;  

}

list = list->next;

node->next = q; /*完成插入动作*/

}

}

/************************************************************************/

/*

合并两个线性表

*/

/************************************************************************/

void mergeList(LinkList  &La, LinkList  &Lb,  LinkList &Lc){

LinkList pa, pb, pc;

pa = La->next;

pb = Lb->next;

Lc =  pc = La;

while (pa && pa) {

if (pa->data > pb->data) {

pc->next = pb;

pc = pb;

pb =pb->next;

}else{

pc->next = pa;

pc = pa;

pa =pa->next;

}

}

pc->next = pa? pa :pb;

free(Lb);

}

/************************************************************************/

/* 打印list

*/

/************************************************************************/

void printList(LinkList  L){

printf("当前值:");

LinkList p;

p = L->next;

while(p){

printf("%d ", p->data);

p = p->next;

}

printf("\r\n");

}

void main()

{

LinkList  La,Lb,Lc;

ElemType e;

int init,i;

printf("LA:\r\n"); 

initList(La);

createList(La, 5);

insertList(La, 7,  3); 

printList(La);

deleteListElem(La, 3,  e); 

printList(La);

InsertSort(La);

printList(La);

printf("Lb:\r\n"); 

initList(Lb);

createList(Lb, 4);

InsertSort(Lb);

printList(Lb);

printf("Lc:\r\n");

initList(Lc);

mergeList(La,   Lb,   Lc);

printList(Lc);

}

给我留言

留言无头像?