顺序表和链表

数据结构=结构定义+结构操作

1.顺序表

1	2	3	4	5

size=9; length=5; data_type=xxx;

(1）顺序表的插入操作

1	2	6	3	4	5

size=9; length=6; data_type=xxx;

（2）顺序表的删除操作

1	2	6	3	4	5

size=9; length=5; data_type=xxx;

（3）顺序表的代码演示

  #include<stdio.h>
  #include<stdlib.h>
  #include<time.h>
//结构定义  
typedef struct Vector{
    int *data;
    int size,length;
}Vector;
//初始化一个可以存储n个元素的顺序表(顺序表的初始化操作)
Vector *init(int n)
{
    Vector *vec=(Vector *)malloc(sizeof(Vector));
    vec->data=(int *)malloc(sizeof(int)*n);
    vec->size=n;
    vec->length=0;
    return vec; 
}
//顺序表的销毁工作
void clear(Vector *vec)
{
	if(vec==NULL)return ;
    free(vec->data);
    free(vec);
    return ;
}
//扩容操作
int expand(Vector *vec)
{
    vec->size*=2;
    vec->data= (int*)realloc(vec->data,sizeof(int)*vec->size)；
    return 1;
}
//插入
int insert(Vector *vec,int ind,int val)
{
    //判断顺序表是否有效
	if(vec==NULL) return 0;//如果数据表是空的（没有空间）则无效
    if(vec->length==vec->size) return 0;//如果数据表已满则无效
    	if(!expand(vec)){
            return 0;
        }
    printf("expand to %d \n",vec->size);//输出扩容的结果
    if(ind<0||ind>vec->length) return 0;//位置超前或溢出表空间则无效
    //数据表中插入元素，注意要从后往前插入，否则会破坏原有数据
    for(int i=vec->length-1;i>=ind;i--){
        vec->data[i]=vec->data[i-1];
    }
    vec->data[ind]=val;
    vec->length+=1;
    return 1;//返回1表示插入动作完成
    
}
//删除
int erase(Vector *vec,int ind)
{
    if(vec==NULL) return 0;
    if(vec->length==0) return 0;
    if(ind<0||ind>=vec->length) return 0;
    for(int i=ind+1;i<=vec->length;i++){
        vec->data[i-1]=vec->data[i];
    }
    vec->length-=1;
    return 1;
    
}
//输出顺序表
void output(Vector *vec)
{
    printf("Vector(%d)=[",vec->length);
    for(int i=0;i<=vec->length;i++){
    if(i!=0){
        printf(", ");
    }
	printf("%d",vec->data[i]);
    }
    printf("]\n");
    return ;
}

  int main()
  {
      srand(time(0));//按照时间取随机数，需要导入<time.h>
  	  #define MAX_OP 20 //定义一个最大选项的宏
      Vector *vec=init(1);//初始化顺序表
      int op,ind,val;
      for(int i=0;i<=MAX_OP;i++){
          op=rand()%2;//随机产生0或1
          ind=rand()%(vec->length+1);
          val=rand()%100;//随机产生1到100的数
         switch(op){
             case 0:{
                 printf("inset %d at %d to vector\n",val,ind);
                 insert(vec,ind,val);
             }break;
             case 1:{
                 printf("erase item %d from vector\n",ind);
                 erase(vec,ind);
             }break;
                 
         }
          output(vec);//每进行一次操作之后输出一次数表
      }
  
  	return 0;
  }

运行结果：

(4)关于realloc函数

a. realloc函数先尝试在原来的数表后面去扩展空间 ,如果成功，则返回原来的首地址（记为p)

b. 如果原有数表之后无法再继续扩充，realloc函数会调用malloc函数，真正地去重新分配空间，然后把原来空间中的数据拷贝到新的空间，最后再返回新申请空间的首地址 （p’)

c. malloc申请新的空间并完成拷贝之后会自动释放原来p的空间

d. 如果申请p’的步骤都失败了，realloc不会释放原来的空间，会返回一个空地址（无法找到原来地址，会造成内存泄漏）

e. 上述bug解决办法：

int new_size=vec->size*2;
int *p=(int*)realloc(vec->data,sizeof(int)*new_size);//新建一个指针存储realloc的返回地址
if(p==NULL) return 0; 
vec->size=new_size;
vec->data=p;
return 1;

2.链表

链表的插入

单向循环链表

头指针存储的是尾结点的地址

链表的代码演示

#define _CRT_SECURE_NO_WARNINGS 
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
//定义链表结点
typedef struct ListNode
{
	//数据域
	int data;
	//指向下一个结点的指针域
	struct ListNode* next;
}ListNode;
//定义链表结构
typedef struct LinkList
{
	//指向头结点的指针
	ListNode head;
	//链表的总长度
	int length;
}LinkList;
//初始化链表结点
ListNode* init_ListNode(int val)
{
	//定义一个指针指向链表结点 
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	//给链表赋值
	p->data = val;
	p->next = NULL;
	return p;
}
//初始化链表
LinkList* init_LinkList()
{
	//定义一个指向链表的指针 
	LinkList* l = (LinkList*)malloc(sizeof(LinkList));
	//初始化链表的头指针 
	l->head.next = NULL;
	//开始链表的总长度为0 
	l->length = 0;
	return l;
}
int insert(LinkList* l, int ind, int val)
{
	if (l == NULL)return 0;
	if (ind<0 || ind>l->length)return 0;
	ListNode* p = &(l->head), * node = init_ListNode(val);
	while (ind--) {
		p = p->next;
	}
	node->next = p->next;
	p->next = node;
	l->length += 1;
	return 1;
}

//销毁结点 
void clear_ListNode(ListNode* node)
{
	if (node = NULL)return;
	free(node);
	return;
}
//销毁链表 结点 
void clear_LinkList(LinkList* l)
{
	if (l == NULL) return;
	ListNode* p = l->head.next, * q;
	while (p) {
		q = p->next;
		clear_ListNode(p);
		p = q;
	}
	free(l);
	return;
}
//销毁链表
int erase(LinkList* l,int ind)
{
	if (l == NULL)return 0;
	if (ind < 0|| ind >= l->length) return 0;
	ListNode* p = &(l->head), * q;
	while (ind--) {
		p = p->next;
	}
	q = p->next->next;
	clear_ListNode(p->next);
	p->next = q;
	l->length -= 1;
	return 1;

}
void output(LinkList* l)
{
	printf("LinkList(%d)=", l->length);
	ListNode* i =l->head.next;
	for (i; i; i = i->next) {
		printf("%d -> ", i->data);
	}
	printf("NULL\n");
	return;
}
#define MAX_OP 30
int mian()
{
	LinkList* l = init_LinkList();
	srand(time(0));
		int i = 0;
	for (i = 0; i < MAX_OP; i++) {
		int op = rand() % 4;
		int ind = rand() % (l->length + 1);
		int val = rand() % 100;

		switch (op) {
		case 0:
		case 1:
		case 2: {
			printf("insert %d at %d to LinkList=%d",
				val, ind, insert(l, ind, val));
			break;
		}
		case 3: {
			printf("erase item at %d from LinkList=%d", ind,
				erase(l, ind));
			break;
		}
		}
		output(l);
		printf("\n");
	}


	return 0;
}