大多数编程语言中的数组, 无论静态还是动态, 都可以被归纳为SequenceList, 在Java中, SequenceList被实现为ArrayList. 而LinkedList也在Java的集合框架中存在(就叫LinkedList).
优缺点
- SqList知道index下标以后(也叫做随机访问), 访问一个元素是O(1)时间; 但是删除, 和插入元素的时候, 需要移动大量的元素, 时间是O(n);
- 对比之下, LinkedList没有下标一说, 随机访问一个元素的时间是O(n); 但是删除头和尾部的元素(有L和r头尾指针情况下), 时间是O(1)的. 但是, 在删除List中非头尾, 某index要求位置的元素的时候, 由于要先获取到元素所在前一位的节点, 其实等于要先做一次随机访问, 要花O(n)时间.
SqList
要点:
- 有index; 且下标index从0开始;
- 强健性: 先检查解决list的空满和输入合法性问题, 再开始操作;
- 同步性: 每个方法都要关注成员属性length和listsize的同步更新
/*typedef 类型定义*/
//length用来描述当前长度, listsize用来描述最大容纳SIZE;
typedef struct {
ElemType *elem;
int length;
int listsize;
}SqList;
/*InitSqList*/
//初始化的时候,先检查是否成功(否则exit),然后要顾及到每个成员属性的初始化
Status InitSqList(SqList *L) {
L->elem = (ElemType *)malloc(SIZE*sizeof(ElemType));
if (!L->elem) {printf("Init OVERFLOW\n");exit(OVERFLOW);}
L->length = 0;
L->listsize = SIZE;
return 0;
}
/*InsertSqList*/
//插入的时候,先检查一下是否满了, 否则先移动插入位置到结尾的所有元素往后一位, 然后再插入;
//要顾及成员属性如length和listsize的变化;
Status InsertSqList(SqList *L, int index, ElemType e) {
if (L->length>=L->listsize) {
printf("Reallocate memory\n");
L->elem = (ElemType *)realloc(L->elem, (SIZE+INCREMENT)*sizeof(ElemType));
if (!L->elem) {printf("Insert OVERFLOW\n");exit(OVERFLOW);}
L->listsize += INCREMENT;
}
int i = 0;
for (i=L->length; i>index; i--) { //从后往前,每个元素保存前一位的值,遍历到插入位置index+1的地方就可以了;
//注意, 因为是插入, 所以要从arr[length] = arr[length-1]开始; 比如现在五个数arr[0]~arr[4],得先arr[5]=arr[4];
L->elem[i] = L->elem[i-1];
}
L->elem[i] = e;
printf("elem[%d]%d \n",i,L->elem[i]);
L->length++;
return 0;
}
/*RemoveElementInSqList*/
//删除的时候,先检查下是否空了
//(其实数据结构就是这些讨论,初始化检查成功了吗,插入检查满了,删除和获取的时候检查空了吗)
//然后直接通过arr[i] = arr[i+1]的办法来实现删除和移动;
Status RemoveElementInSqList(SqList *L, int index) {
if (index<0 || index>=L->listsize) {printf("Invalid input\n"); return ERROR;}
if (L->length<=0) {printf("Empty List\n"); return ERROR;}
int i = 0;
for (i=index; i<L->length-1; i++) { //最多遍历到arr[length-2]的位置,原先最后一位是arr[length-1];
L->elem[i] = L->elem[i+1];
}
L->length--;
return 0;
}
/*OutputSqList*/
//遍历一下
Status OutputSqList(SqList *L) {
int i=0;
for (i=0; i<L->length; i++) {
printf("%d ",L->elem[i]);
}
printf("\n");
return 0;
}
附上一些常量的定义, 以后没有说的话, 都默认代码头部是这些东西;
#include <stdio.h>
#include <stdlib.h>
#define ElemType int
#define Status int
#define OK 0
#define ERROR -1
#define OVERFLOW -1
#define SIZE 3
#define INCREMENT 1
检验数据结构正确性的main函数;
int main() {
int input[5] = {10, 20, 30, 40, 50};
SqList L;
InitSqList(&L);
int i = 0;
for (i=0; i<5; i++) {
InsertSqList(&L, 0, input[i]);
}
OutputSqList(&L);
RemoveElementInSqList(&L, 3); //下标是从0开始的;
OutputSqList(&L);
return 0;
}
LinkedList
- 没有index, 因此需要从头开始找到一个元素的位置才能进行获取, 插入, 删除的操作;
- 指针在循环中的指向: 要非常注意循环中p到底指到数组List的哪一位的问题, 要算好j循环到哪里了;
- 强健性: 先检查解决list的空满和输入合法性问题, 再开始操作;
/*类型定义*/
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LList;
LinkedList的类型定义相当简单, 而真正难点在节点的操作;
/*创建链表L*/
//从头加入的初始化; 注意: 输入的时候需要倒序;
LList Creat_LL( ) {
LList L = NULL;
LNode *p;
printf("Input elements: ");
ElemType flag = -99;
ElemType value;
scanf("%d",&value);
while (value!=flag) {
p = (LNode *)malloc(sizeof(LNode));
p->data = value;
p->next = L;
L = p;
scanf("%d",&value);
}
return L; //此处记得要返回L;
}
//从尾加入的初始化
//我们现在是只有头指针, 而没有头结点的情况
LList Creat_LL( ) {
LList L = NULL;
LNode *p, *r = L; //需要添加一个r指向尾巴
printf("Input elements: ");
ElemType flag = -99;
ElemType value;
scanf("%d",&value);
while (value!=flag) {
p = (LNode *)malloc(sizeof(LNode));
if (L==NULL) {L=p;} //单独要判断一下是否在指向第一个节点
else {r->next = p;} //如果不是第一个节点的情况, 让原先的尾巴节点;
p->data = value; //成员属性赋值;
p->next = NULL; //成员赋值
r = p; //让尾指针指向最后一个新加的元素;
scanf("%d",&value);
}
return L; //此处记得要返回L;
}
/*取节点操作*/
//能够大大简化后面insert和delete的操作;
LNode *Get_LL(LList L, int i) {
int j = 0;
LNode *p = L;
while (p->next && j<i) { //非常关键的一行
p = p->next; j++;
}
if (j<i) {return NULL;} else {return p;}
}
/* 需要理解当循环发现j=i的时候会跳出, 使得p指向前一个元素;
或者是p->next为空的时候跳出, 使得最后j<i, 也就是说前一个节点存在,
而arr[i]位置节点不存在的情形将会被return NULL,
因为取不到arr[i], 而j=i且下一位没有节点,
也就是最后一位存在的节点刚好就是arr[i]的情形将会被允许; */
/*在链表的第i个位置上插入e*/
//思路: 检查是否有前一个元素, 然后给新节点分配一个LNode大小的内存, 并赋予各项值(e, NULL);
//@L:要插入的链表
//@i:要插入的位置index
//@e:要插入的element
LList Insert_LL(LList L, int i, int e) {
LNode *p = Get_LL(L, i-1); //获取前一个节点;
if (p==NULL) {
printf("ERROR");
return NULL;
} else {
LNode *q = (LNode *)malloc(sizeof(LNode));
q->data = e;
q->next = p->next;
p->next = q;
return L;
}
}
/*删除链表第i个位置上的元素*/
//思路: 先判断是否为空, 不为空再利用p->next = p->next->next;
//@L: LinkedList
//@i: index
LList Delete_LL(LList L, int i) {
LNode *p;
p = Get_LL(L, i-1);
if (p == NULL) {
printf("ERROR!");
return NULL;
} else {
p->next = p->next->next;
}
return L;
}
/*输出链表L*/
//思路: 先检查是否为空, 然后输出;
void Output_LL(LList L) {
if (L == NULL) {printf("Empty LinkedList!\n");}
else {
LNode *p = L;
while (p) {
printf("%d\t",p->data);
p = p->next;
}
printf("\n");
}
}
提示: 测试数据, 注意需要把不同实现的方法给注释掉一个;
int main(){
//20,22,23,24,24
LList L2;
L2=Creat_LL( );
Output_LL(L2);
L2=Insert_LL(L2, 1, 21);
Output_LL(L2);
L2=Delete_LL(L2, 1);
Output_LL(L2);
return 0;
}
