线性表
基本操作
Initlist(&L):初始化表
Length(L):求表长
LocateElem(L,e):按值查找操作
GetElem(L,i):按位查找操作
ListInsert(&L,i,e):插入操作
ListDelete(&L,i,&e):删除操作
PrintList(L):输出操作
Empty(L):判空操作
DestroyList(&L):销毁操作
顺序表
静态分配的顺序表存储结构
#define Maxsize 50
typedef struct{ElemType data[Maxsize];int length;
}SqList;
动态分配的顺序表存储结构
#define InitSize 100
typedef struct{ElemType *data;int Maxsize,length;
}SeqList;
L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);或
L.data=new ElemType[InitSize];
增加动态数组的长度
#include <stdlib.h>
#define InitSize 10
typedef struct{int *data;int Maxsize,length;
}SeqList;int main(){SeqList L;IniList(L);...IncreaseSize(L,5);return 0;
}//初始化一个动态数组
void InitList(SeqList &L){L.data=(int*)malloc(InitSize*sizeof(int));L.length=0;L.MaxSize=InitSize;
}//增加动态数组的长度
void IncreaseSize(SeqList &L,int len){int *p=L.data;L.data=(int*)malloc((L.MaxSize+len)*sizeof(int));for(int i=0;i<L.length;i++){L.data[i]=p[i];//注意访问p指针指向的数组}L.MaxSize=L.MaxSize+len;free (p);
}
静态分配顺序表的初始化
void InitList(SqList &L){for(int i=0;i<MaxSize;i++){L.data[i]=0;}L.length=0;
}
或者
void InitList(sqList &L){L.length=0;
}
动态分配顺序表的初始化
void InitList(SeqList &L){L.data=(ElemType*)malloc(InitSize*sizeof(ElemType));L.length=0;L.MaxSize=InitSize;
}
插入操作(位置在1~L.length+1之间)
bool ListInsert(SqList &L,int i,ElemType e){if(i<1||i>L.length+1)return false;if(L.length>=MaxSize)//存储空间满return false;for(int j=L.length;j>=i;j--)L.data[j]=L.data[j-1];//第i个元素后的元素后移L.data[i-1]=e;L.length++;return true;
}
删除操作(位置在1~L.length之间)
bool ListDelete(SqList &L,int i,ElemType &e){if(i<1||i>L.length) return false;e=L.data[i-1];for(int j=i;j<L.length;j--)L.data[j-1]=L.data[j];//第i个元素后的元素前移L.length--;return true;
}
按值查找
int LocateElem(SqList L,ElemType e){int i;for(i=0;i<L.length;i++)//若为i<InitSize,则初始化要全部初始化为0,防止脏数据影响if(L.data[i]==e) return i+1;//返回位序i+1return 0;
}
按位查找(静态分配和动态分配一样)
ElemType GetElem(SqList L,int i){return L.data[i-1];
}
补充:结构体的比较不能直接用==,应该一个一个元素比较。
链表
单链表
单链表节点结构
typedef struct LNode{ElemType data;struct LNode *next;
}LNode,*LinkList;
相当于
struct LNode{ElemType data;struct LNode *next;
};
typedef struct LNode LNode;
typedef struct LNode *LinkList;LNode *L;//表明这是一个指向单链表第一个结点的指针,强调结点
LinkList L;//同上,更强调链表
单链表的初始化及判空(带头结点)
bool InitList(LinkList &L){L=(LNode*)malloc(sizeof(LNode));//分配第一个头结点if(L==NULL) return false; //内存不足,分配失败L->next=NULL;return true;
}bool Empty(LinkList L){if(L->next==NULL) return true;else return false;
}
单链表的初始化及判空(不带头结点)
bool InitList(LinkList &L){L=NULL;return true;
}bool Empty(LinkList L){if(L==NULL) return true;else return false;
}
或者
bool Empty(LinkList L){return (L==NULL):
}
求表长操作(带头结点)
int length(LinkList L){int len=0;//计数变量LNode* p=L;while(p->next!=NULL){p=p->next;len++;}return len;
}
按序号查找
LNode* GetElem(LinkList L,int i){if(i<0) return NULL;LNode *p=L;int j=0;//记录当前结点的位序,头结点为第0个结点,方便把结点插在第1个位置while(p!=NULL&&j<i){p=p->next;j++;}return p;//返回指向第i个结点的指针或NULL
}
按值查找
LNode *LocateElem(LinkList L,ElemType e){LNode *p=L->next;while(p!=NULL&&p->data!=e){p=p->next;}return p;//找到则返回该结点指针,否则返回NULL
}
按位序插入(带头结点)
bool ListInsert(LinkList &L,int i,ElemType e){if(i<1) return false;LNode *p=L;int j=0;//头结点是第0个结点while(p!=NULL&&j<i-1){//找到第i-1个结点p=p->next;j++;}if(p==NULL) return false;//i值不合法LNode *s=(LNode*)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;return true;
}
按位序插入(不带头结点)
bool ListInsert(LinkList &L,int i,ElemType e){if(i<1) return false;if(i==1){//仅第1一个结点与带头结点的操作不同LNode *s=(LNode*)malloc(sizeof(LNode));s->data=e;s->next=L;L=s;return true;}LNode *p=L;int j=1;//没有头结点了while(p!=NULL&&j<i-1){//找到第i-1个结点p=p->next;j++;}if(p==NULL) return false;//i值不合法LNode *s=(LNode*)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;return true;
}
指定结点的后插操作
bool InsertNextNode(LNode *p,ElemType e){//在p结点之后插入元素eif(p==NULL) return false;LNode *s=(LNode*)malloc(sizeof(LNode));if(s==NULL) return false; //内存分配失败s->data=e;s->next=p->next;p->next=s;return true;
}
指定结点的前插操作
bool InsertPriorNode(LNode *p,ElemType e){if(p==NULL) return false;LNode *s=(LNode*)malloc(sizeof(LNode));if(s==NULL) return false;//内存分配失败s->next=p->next;p->next=s;s->data=p->data;p->data=e;return true;
}
按位序删除(带头结点)