数据结构第2天作业 8月3日

 单向链表

typedef int datatype;   //由于有效数据不一定是正数，所以将数据重命名。typedef struct lklst{   //不能是无名结构体了，因为定义指针域的时候需要使用union{int len;                   //头结点时候使用；datatype data;           //有效数据结点时候使用；}text;                   //数据域，存储数据struct lklst *next;     //指针域，指向下一个结点，存储下一个结点的首地址
}Linklist;

创建空的单链表

Linklist * createlinklist(void){//在堆空间中申请头结点//判断是否生成 成功Linklist *link=(Linklist*) malloc(sizeof(Linklist));//malloc申请堆空间，返回的是void*类型所以需要强转成需要的类型if(link == NULL){printf("堆空间申请失败");return NULL;}link->next=NULL;link->text.len=0;return link;
}

头插

//头插法插入数据
void insert_linklistByHead(Linklist *head,datatype data){//创建节点Linklist * temp=(Linklist*) malloc(sizeof(Linklist));if(temp == NULL){printf("堆空间申请失败");return ;}temp->next=NULL;temp->text.data=data;//temp->next=head->next;head->next=temp;//更新头节点数据的长度head->text.len++;return;
}

尾插

//尾插法插入数据
void insert_linklistByEnd(Linklist *head,datatype data){//创建节点Linklist * temp=(Linklist*) malloc(sizeof(Linklist));if(temp == NULL){printf("堆空间申请失败");return ;}temp->next=NULL;temp->text.data=data;Linklist * read =head;//找到尾节点while(read->next!=NULL){read =read->next;}read->next=temp;//更新长度head->text.len++;
}

按位置插入

//按位置插入
void insert_linklistByPosition(Linklist *head,datatype data,int n) {if (n < 1) {printf("非法数据\n");return;}Linklist *p = head;for (int i=0;i<n-1;i++) {p=p->next;if(p==NULL){printf("非法数据\n");return;}}Linklist * temp=(Linklist*) malloc(sizeof(Linklist));if(temp == NULL){printf("堆空间申请失败");return ;}temp->text.data=data;temp->next = NULL;
//将temp插入到p结点的后一个位置temp->next=p->next;temp->text.data=data;p->next=temp;//更新长度head->text.len++;return;
}

头删

void delete_linklistByHead(Linklist *head){//判断链表是否为空if(head->next==NULL)return;//先将要释放的结点地址另存Linklist * temp = head->next;//要释放结点中存储下一个结点的地址，给头结点head->next=temp->next;//释放结点free(temp);temp=NULL;//更新长度head->text.len--;return ;
}

尾删

//尾删
void delete_linklistByEnd(Linklist *head){//判断链表是否为空if(head->next==NULL)return;//寻找倒数第二个结点Linklist * temp =head;while(temp->next->next != NULL) {temp = temp->next;}//释放结点free(temp->next);temp->next = NULL;//更新长度head->text.len--;
}

按位置删除

//按位置删除
void delete_linklistByPosition(Linklist *head,int n){if(head->next==NULL){printf("非法数据\n");return;}if(n<1){printf("非法数据\n");return;}//找到要删除结点的前一个节点位置Linklist* p = head;for(int i=0;i<n-1;i++)p=p->next;if(NULL == p->next){printf("n=%d删除位置非法\n",n);return;}//能运行到这个位置，则说明p指向的是要删除的结点的前一个位置Linklist* temp = p->next;p->next = temp->next;free(temp);temp = NULL;//更新长度head->text.len++;return ;
}

 遍历链表

//遍历链表
void Iterative_list(Linklist *head){//读头节点的数据Linklist * read =head;while(read->next!=NULL){read =read->next;datatype data = read->text.data;printf("%d\t",data);}putchar(10);
}

单向循环链表

typedef int datatype;   //由于有效数据不一定是正数，所以将数据重命名。typedef struct loopklst{   //不能是无名结构体了，因为定义指针域的时候需要使用union{int len;                   //头结点时候使用；datatype data;           //有效数据结点时候使用；}text;                   //数据域，存储数据struct loopklst *next;     //指针域，指向下一个结点，存储下一个结点的首地址
}LoopLinklist;

//创建一个空的单链表
LoopLinklist * create_recurringlinklist(void) {LoopLinklist * head = (LoopLinklist *) malloc(sizeof(LoopLinklist));if (NULL == head){printf("单向循环链表创建失败\n");return NULL;}head->text.len =0;//头结点中记录的链表长度赋值为0head->next =head;//将指针域指向自己return head;
}

头插

//头插
void insert_recurringlinklistByHead(LoopLinklist *head,datatype data){//创建节点LoopLinklist * temp=(LoopLinklist*) malloc(sizeof(LoopLinklist));LoopLinklist * p=head;if(temp == NULL){printf("堆空间申请失败");return ;}temp->text.data=data;temp->next=p->next;head->next=temp;//更新头节点数据的长度head->text.len++;return;
}

尾插

//尾插
void insert_recurringlinklistByEnd(LoopLinklist *head,datatype data){LoopLinklist *temp=(LoopLinklist *) malloc(sizeof (LoopLinklist ));if(temp==NULL){printf("创建失败");return;}LoopLinklist * p=NULL;p=head;while(p->next!=head){p=p->next;}temp->next=head;temp->text.data=data;p->next=temp;head->text.len++;return;
}

按位置插入

void insert_recurringlinklistByPosition(LoopLinklist *head,datatype data,int n){if (n < 1) {printf("非法数据\n");return;}LoopLinklist *p = head;for (int i=0;i<n-1;i++) {p=p->next;if(p==NULL){printf("非法数据\n");return;}}LoopLinklist * temp=(LoopLinklist*) malloc(sizeof(LoopLinklist));if(temp == NULL){printf("堆空间申请失败");return ;}temp->text.data=data;temp->next = NULL;//将temp插入到p结点的后一个位置temp->next=p->next;temp->text.data=data;p->next=temp;//更新长度head->text.len++;return;
}

头删

//头删
void delete_recurringlinklistByHead(LoopLinklist *head){LoopLinklist *temp=head->next;if(head->next==head){printf("链表为空，删除失败");return;}temp=temp->next;free(head->next);head->next=temp;return;
}

尾删

//尾删
void delete_recurringlinklistByEnd(LoopLinklist *head){//判断链表是否为空LoopLinklist *p=head;if(head->next==head){printf("链表为空");return;}//找到倒数第二个结点while(p->next->next!=head){p=p->next;}//free(p->next);p->next=head;//更新长度head->text.len--;return;
}

按位置删除

//位置删除
void delete_recurringlinklistByPosition(LoopLinklist *head,int n){if(head->next==head){printf("非法数据\n");return;}if(n<1){printf("非法数据\n");return;}//找到要删除结点的前一个节点位置LoopLinklist* p = head;for(int i=0;i<n-1;i++)p=p->next;if(p->next==head){printf("n=%d删除位置非法\n",n);return;}//能运行到这个位置，则说明p指向的是要删除的结点的前一个位置LoopLinklist* temp = p->next;p->next = temp->next;free(temp);temp = NULL;//更新长度head->text.len++;return ;
}

遍历链表

//遍历循环单向链表
void Iterative_recurringlinklist(LoopLinklist *head){//读头节点的数据LoopLinklist * read =head;while(read->next!=head){read =read->next;datatype data = read->text.data;printf("%d\t",data);}putchar(10);
}

双向链表

typedef int datatype;   //由于有效数据不一定是正数，所以将数据重命名。typedef struct Dublinklist{   //不能是无名结构体了，因为定义指针域的时候需要使用union{int len;                   //头结点时候使用；datatype data;           //有效数据结点时候使用；}text;                   //数据域，存储数据struct loopklst *prev;  //指针域，指向上一个结点，存储上一个结点的首地址struct loopklst *next;     //指针域，指向下一个结点，存储下一个结点的首地址
}Dublist;

Dublist * create_Dublinklist(void){//判断是否生成 成功Dublist *link=(Dublist*) malloc(sizeof(Dublist));//malloc申请堆空间，返回的是void*类型所以需要强转成需要的类型if(link == NULL){printf("堆空间申请失败");return NULL;}link->prev=NULL;link->next=NULL;link->text.len=0;return link;
}

头插

void insert_DublistByHead(Dublist *head,datatype data){Dublist *temp=(Dublist *) malloc(sizeof (Dublist));if(temp==NULL){printf("堆空间申请失败");return;}Dublist *p=head;temp->text.data=data;//nexttemp->next=head->next;head->next=temp;//prvetemp->prev=head;if(temp->next!=NULL){temp->next->prev=temp;}head->text.len++;return;
}

尾插

void insert_DublistByEnd(Dublist *head,datatype data){Dublist *temp=(Dublist *) malloc(sizeof (Dublist));if(temp==NULL){printf("堆空间申请失败");return;}Dublist *p=head;temp->text.data=data;//找尾部的位置while(p->next!=NULL){p=p->next;}//nexttemp->next=p->next;p->next=temp;//prvetemp->prev=p;//更新长度head->text.len++;return;
}

按位置插入

//按位置插入
void insert_DublistByPosition(Dublist *head,datatype data,int n) {if (n < 1) {printf("非法数据\n");return;}Dublist *p = head;for (int i=0;i<n-1;i++) {p=p->next;if(p==NULL){printf("非法数据\n");return;}}Dublist * temp=(Dublist*) malloc(sizeof(Dublist));if(temp == NULL){printf("堆空间申请失败");return ;}temp->text.data=data;temp->next = NULL;
//将temp插入到p结点的后一个位置temp->next=p->next;temp->text.data=data;p->next=temp;//更新长度head->text.len++;return;
}

头删

//头删
void delete_DublistByHead(Dublist *head){if(head->next==NULL){printf("非法数据\n");return;}Dublist * temp=head->next;head->next=temp->next;head->next->prev=head;free(temp);temp=NULL;return;
}

尾删

void delete_DublistByEnd(Dublist *head){Dublist * p=head;//判断链表是否为空if(head->next==NULL)return;//寻找倒数第二个结点Dublist * temp =head;while(temp->next->next != NULL) {temp = temp->next;}//释放结点free(temp->next);temp->next = NULL;//更新长度head->text.len--;return;
}

按位置删除

//按位置删除
void delete__DublistByPosition(Dublist*head,int n){if(head->next==NULL){printf("非法数据\n");return;}if(n<1){printf("非法数据\n");return;}//找到要删除结点的前一个节点位置Dublist* p = head;for(int i=0;i<n-1;i++)p=p->next;if(NULL == p->next){printf("n=%d删除位置非法\n",n);return;}//能运行到这个位置，则说明p指向的是要删除的结点的前一个位置Dublist* temp = p->next;p->next = temp->next;free(temp);temp = NULL;//更新长度head->text.len++;return ;
}