#define N 8
typedef struct elem
{
	int element;//每個(gè)數(shù)據(jù)元素中的數(shù)據(jù)項(xiàng)
}sel;
typedef struct seq
{
	sel* arr;//動(dòng)態(tài)開辟的線性表空間的首地址，通過這個(gè)指針訪問到線性表空間
	int size;//當(dāng)前已經(jīng)使用了的空間的個(gè)數(shù)
	int capacity;//當(dāng)前的最大的數(shù)據(jù)元素容量
}sl;

void initsequence(sl* a)//初始化動(dòng)態(tài)順序表
{
	a->size = 0;//數(shù)組元素以0開始計(jì)算,size是最后一個(gè)元素的下標(biāo)，不是元素總數(shù)量
	a->capacity = N;//N在上面已經(jīng)define了
	a->arr = (sel*)malloc(sizeof(int) * N);
}

void checkcapacity(sl* a)//檢查是否需要擴(kuò)容
{
	if (a->size +1== a->capacity)
	{
		a->capacity *= 2; 
		a->arr =(sel*) realloc( a->arr,sizeof(int) * (a->capacity));
		if (a->arr == NULL)
		{
			printf("realloc defect");
			exit(-1);
		}
	}
}

void sequpushfront(sl* a,sel* ele)//尾插法
{
	checkcapacity(&a);//檢查是否需要擴(kuò)容
	*(a->arr + a->size) =ele->element;//因?yàn)槲抑辉O(shè)置了一個(gè)int類型的如果數(shù)據(jù)元素中有多個(gè)數(shù)據(jù)項(xiàng)向下看
	++(a->size);
}

void sequpushfront(sl* a,sel* ele)//尾插法
{
	checkcapacity(&a);//檢查是否需要擴(kuò)容
	(a->arr + a->size)->n =ele->element;//假設(shè)是有多個(gè)數(shù)據(jù)項(xiàng)就這樣依次匹配（a->arr + a->size）已經(jīng)訪問到每個(gè)元素的地址再->n訪問到相應(yīng)元素的空間進(jìn)行存儲(chǔ)。
	++(a->size);
}

void sequpushback(sl* a, int n)//頭插法
{
	checkcapacity(&a);//檢查是否需要擴(kuò)容
	int head = 0;
	int end = a->size;
	while (end>=head)
	{
		*(a->arr + end + 1) = *(a->arr + end);
		
		--end;
	}
	++(a->size);
	*(a->arr + head) = n;
}

void sequpushback(sl* a, sel* ele)//頭插法
{
	checkcapacity(&a);//檢查是否需要擴(kuò)容
	int head = 0;
	int end = a->size;
	while (end>=head)
	{
		*(a->arr + end + 1) = *(a->arr + end);
		
		--end;
	}
	++(a->size);
	*(a->arr + head) = ele->element;
}

void sequpopmid(sl* a, int n)//中間刪除，n是要?jiǎng)h除的位置
{
	assert(n>=0&&n<=a->size);
	for (int i = n ; i < a->size-1; i++)
	{
		*(a->arr + i) = *(a->arr + i + 1);
	}
	--(a->size);
}

void sequpushmid(sl* a, int n,sel* ele)//中間添加
{
	assert(n>=0&&n=<a->size+1);//要在有效位置添加
	checkcapacity(&a);//檢查是否需要擴(kuò)容
	int head = n;
	int end = a->size;
	while (end>=head)
	{
		*(a->arr + end + 1) = *(a->arr + end);
		--end;
	}
	++(a->size);
	*(a->arr + head) = ele->element;
}

#include "linkedlist.h"
void test()
{
	list* head;
	list* last;
	initLinkedlist(&head,&last);
	pushlast(&last, 1);//尾插法
	pushlast(&last, 2);
	pushlast(&last, 3);
	pushlast(&last, 4);
	pushfront(&head, 5);//頭插法
	pushfront(&head, 8);//頭插法
	pushfront(&head, 7);//頭插法
	pushfront(&head, 6);//頭插法
	popchoice(&head, 0);//任意位置刪除
	//poshposition(&head, 3);//任意位置插入
	printlist(&head);//打印
}
int main(void)
{
	test();
	return 0;
}

void initLinkedlist(list** head,list** last)//初始化鏈表
{
	*head = (list*)malloc(sizeof(list));
	(*head)->next = NULL;
	*last=*head;
}

void pushlast(list** last, int num)//尾插法
{
	list* new = (list*)malloc(sizeof(list));
	new->n = num;
	new->next = (*last)->next;
	(*last)->next = new;
	(*last) = new;
}

void pushfront(list** head, int num)//頭插法
{
	list* new = (list*)malloc(sizeof(list));
	new->n = num;
	new->next = (*head)->next;
	(*head)->next = new;
}

void printlist(list** head)//打印
{
	list* p = (*head)->next;
	while (p)
	{
		printf("%d ", p->n);
		p = p->next;
	}
}

void popchoice(list** head, int pos)//任意位置刪除
{
	assert(pos<8&pos>=0);
	int i = 0;
	list* pre = *head;
	list* cur = (*head)->next;
	while (i < pos)
	{
		pre = cur;
		cur = cur->next;
		i++;
	}
	pre->next = cur->next;
	free(cur);
}

#include "doubly_Linkedlist.h"
void doublelinkedlist1()
{
	doulink head;
	initlinkedlist(&head);//初始化雙向鏈表
	LinkedlistFrontPush(&head, 1);//頭插法
	LinkedlistFrontPush(&head, 2);//頭插法
	LinkedlistFrontPush(&head, 3);//頭插法
	LinkedlistFrontPush(&head, 4);//頭插法
	LinkedlistFrontPush(&head, 5);//頭插法
	LinkedlistBackpush(&head, 6);//尾插法
	LinkedlistBackpush(&head, 7);//尾插法
	LinkedlistBackpush(&head, 8);//尾插法
	LinkedlistBackpush(&head, 9);//尾插法
	LinkedlistBackpush(&head, 10);//尾插法	
	LinkedlistFrontPop(&head);//頭刪
	LinkedlistFrontPop(&head);//頭刪
	LinkedlistFrontPop(&head);//頭刪
	LinkedlistBackPop(&head);//尾刪
	LinkedlistBackPop(&head);//尾刪
	LinkedlistBackPop(&head);//尾刪
	LinkedlistBackPop(&head);//尾刪
	LinkedlistBackPop(&head);//尾刪
	LinkedlistPrint(&head);//打印鏈表	
}
int main(void)
{
	doublelinkedlist1();
}

void initlinkedlist(doulink* head)//初始化雙向鏈表
{
	(*head).next = head;
	(*head).prev = head;
}

void LinkedlistFrontPush(doulink* head, lint n)//頭插法
{
	doulink* newnode = (doulink*)malloc(sizeof(doulink));
	newnode->num = n;
	doulink*phead=(*head).next;//原頭節(jié)點(diǎn) 
	newnode->next = phead;//新的后驅(qū)指針接入下一個(gè)
	(*head).next = newnode;//將哨兵鏈接新結(jié)點(diǎn)
	newnode->prev = head;//新結(jié)點(diǎn)的前驅(qū)指針指向哨兵
	phead->prev = newnode;//原頭結(jié)點(diǎn)的前驅(qū)指針指向新的頭節(jié)點(diǎn)
}

void LinkedlistBackpush(doulink* head, lint n)//尾插法
{
	doulink* newnode = (doulink*)malloc(sizeof(doulink));
	newnode->num = n;
	doulink* plast = (*head).prev;//找到尾結(jié)點(diǎn)
	newnode->prev = plast;//新的尾接入原尾結(jié)點(diǎn)
	newnode->next = plast->next;//新接入哨兵
	plast->next = newnode;//原尾結(jié)點(diǎn)next指向新的尾
	(*head).prev = newnode;//頭節(jié)點(diǎn)的prev指向新的尾結(jié)點(diǎn)，形成閉環(huán)
}

void LinkedlistBackPop(doulink* head)//尾刪
{	
	doulink* last = (*head).prev;//找到要?jiǎng)h除的尾結(jié)點(diǎn)
	doulink* llast = last->prev;//找到刪除后的新的尾結(jié)點(diǎn)
	if (last == head)
	{
		printf("Empty List\n");
		return;
	}
	(*head).prev = llast;//改變哨兵結(jié)點(diǎn)prev指向
	llast->next = last->next;//讓新的尾結(jié)點(diǎn)的next接入哨兵
	free(last);//刪除內(nèi)存
}

void LinkedlistFrontPop(doulink* head)//頭刪
{
	doulink* phead = (*head).next;
	doulink* second = phead->next;
	if (phead == head)
	{
		printf("Empty List\n");
		return;
	}
	second->prev = phead->prev;
	(*head).next = second;
	free(first);
}

#include "doubly_Linkedlist.h"
void initlinkedlist(doulink* head)//初始化雙向鏈表
{
	(*head).next = head;
	(*head).prev = head;
}
void LinkedlistFrontPush(doulink* head, lint n)//頭插法
{
	doulink* newnode = (doulink*)malloc(sizeof(doulink));
	newnode->num = n;
	doulink*phead=(*head).next;//原頭節(jié)點(diǎn) 
	newnode->next = phead;//新的后驅(qū)指針接入下一個(gè)
	(*head).next = newnode;//將哨兵鏈接新結(jié)點(diǎn)
	newnode->prev = head;//新結(jié)點(diǎn)的前驅(qū)指針指向哨兵
	phead->prev = newnode;//原頭結(jié)點(diǎn)的前驅(qū)指針指向新的頭節(jié)點(diǎn)
}
void LinkedlistBackpush(doulink* head, lint n)//尾插法
{
	doulink* newnode = (doulink*)malloc(sizeof(doulink));
	newnode->num = n;
	doulink* plast = (*head).prev;//找到尾結(jié)點(diǎn)
	newnode->prev = plast;//新的尾接入原尾結(jié)點(diǎn)
	newnode->next = plast->next;//新接入哨兵
	plast->next = newnode;//原尾結(jié)點(diǎn)next指向新的尾
	(*head).prev = newnode;//頭節(jié)點(diǎn)的prev指向新的尾結(jié)點(diǎn)，形成閉環(huán)
}
void LinkedlistFrontPop(doulink* head)//頭刪
{
	doulink* phead = (*head).next;
	doulink* second = phead->next;
	if (phead == head)
	{
		printf("Empty List\n");
		return;
	}
	second->prev = phead->prev;
	(*head).next = second;
}
void LinkedlistBackPop(doulink* head)//尾刪
{
	doulink* last = (*head).prev;//找到要?jiǎng)h除的尾結(jié)點(diǎn)
	doulink* llast = last->prev;//找到刪除后的新的尾結(jié)點(diǎn)
	if (last == head)
	{
		printf("Empty List\n");
		return;
	}
	(*head).prev = llast;//改變哨兵結(jié)點(diǎn)prev指向
	llast->next = last->next;//讓新的尾結(jié)點(diǎn)的next接入哨兵
	free(last);
}
void LinkedlistPrint(doulink* head)//打印鏈表
{
	doulink* cur = (*head).next;
	while (cur != head)
	{
		printf("%d ", cur->num);
		cur = cur->next;
	}
}

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int lint;
typedef struct doulinked
{
	lint num;
	lint* prev;
	lint* next;
}doulink;
void initlinkedlist(doulink* head);//初始化雙向鏈表
void LinkedlistFrontPush(doulink* head, lint n);//頭插法
void LinkedlistBackpush(doulink* head, lint n);//尾插法
void LinkedlistFrontPop(doulink* head);//頭刪
void LinkedlistBackPop(doulink* head);//尾刪
void LinkedlistPrint(doulink* head);//打印鏈表