——主要参考了中国大学MOOC数据结构课程的内容
数据名称:线性表(List)
数据对象集:线性表是个元素构成的有序序列
操作集:线性表,整数i表示位置,元素,线性表的基本操作有:
- List MakeEmpty():初始化一个空线性表L;
- ElementType FindKth( int K, List L ):根据位序K,返回相应元素 ;
- int Find( ElementType X, List L ):在线性表L中查找X的第一次出现位置;
- void Insert( ElementType X, int i, List L):在位序i前插入一个新元素X;
- void Delete( int i, List L ):删除指定位序i的元素;
- int Length( List L ):返回线性表L的长度n。
线性表有两种主要实现方法,用数组的方法实现和用链表的方式实现,这个程序可能存在一些bug,但是思路是不变的。
#include<stdio.h>
typedef struct L* List;
struct L{
int max;
int index;
int* data;
};
List MakeEmpty(){
List list= (List)malloc(sizeof(struct L));
list->max = 100;
list->index = -1;
list->data = (int)malloc(list->max*sizeof(int));
return list;
}
int Find(int X, List L){
int i;
for(i=0;i<=L->index;i++){
if(L->data[L->index]==X){
return i;
}
}
return -1;
}
void Delete(int i, List L){
if(i<0||i>L->index){
printf("位置不存在!\n");
return;
}
int j;
for(j=i;j<L->index;j++){
L->data[j] = L->data[j+1];
}
L->index--;
}
int FindKth(int K, List L){
if(K<0||K>L->index){
printf("位置不存在!\n");
return -1;
}
return L->data[K];
}
void Insert(int X,int i,List L){
L->index++;
if(i<0||i>L->index){
printf("插入位置不正确!\n");
return;
}
int j;
if(L->index>=L->max){
int* temp = (int)malloc(sizeof(int)*L->max*2);
for(j=0;j<L->index;j++){
temp[j] = L->data[j];
}
free(L->data);
L->data = temp;
}
for(j=L->index-1;j>=i;j--){
L->data[j+1] = L->data[j];
}
L->data[i] = X;
}
int Length(List L){
return L->index+1;
}
可以看出FindKth需要的时间是O(1), 而Insert和Delete需要的时间是O(N);如果用链表实现,Insert和Delete的开销较小而FindKth开销较大。
#include<stdio.h>
typedef struct node* Node;
struct node{
int data;
struct node* next;
};
void printNode(Node node){
if(node==NULL){
return;
}
Node temp = node;
while(temp!=NULL){
printf("%d ",temp->data);
temp = temp->next;
}
printf("\n");
}
Node findKth(Node node,int kth){
int i = 1;
Node temp = node;
while(i<kth&&temp!=NULL){
temp = temp->next;
i++;
}
if(i==kth&&temp!=NULL){
return temp;
}else{
return NULL;
}
}
Node find(Node node,int data){
Node temp = node;
while(temp!=NULL&&temp->data!=data){
temp = temp->next;
}
return temp;
}
Node createNode(int data){
Node node = (Node)malloc(sizeof(struct node));
node->next = NULL;
node->data = data;
return node;
}
Node insert(Node node,int i,int data){
if(i==1){
Node temp = createNode(data);
temp->next = node;
return temp;
}
Node temp = findKth(node,i-1);
if(temp==NULL){
printf("位置错误!\n");
}else{
Node insert = createNode(data);
Node next = temp->next;
temp->next = insert;
insert->next = next;
}
return node;
}
Node deleteNode(Node node,int i){
if(i==1){
Node temp = node->next;
free(node);
return temp;
}
Node temp = findKth(node,i-1);
if(temp==NULL){
printf("位置错误!\n");
}else{
if(temp->next!=NULL){
Node del = temp->next;
temp->next = del->next;
free(del);
}
}
return node;
}
以前对用链表实现的线程表认识有问题,认为其插入和删除操作开销小,没有意识到在插入或删除的时候,需要去调用FindKth这个开销较大的操作。但是,它还是比用数组实现的要好,因为把数组整体前后挪动的确比较费时间。
网友评论