單連結清單的建立插入與删除

單連結清單的建立插入與删除

/*注意因為建表時用了字元型資料是以輸入數字時隻能輸0~9*/
#include<stdio.h>
#include<stdlib.h>

typedef struct node                           //結點的結構體
{
	int data;                                 //資料域
	struct node *next;                        //指針域
}node, *list;

list HeadCreat();                             //頭插法建立連結清單
list TailCreat();                             //尾插法建立連結清單
void Insert(list head, int x, char value, int length);//向連結清單中特定位置插入一個元素
void Delete(list head, int x, int length);    //删除一個結點
int Length(listhead);                         //統計連結清單的長度 

void print(head);                             //輸對外連結表

int main(void)
{
	list head;
	int x, length;
	char value;

//	head = HeadCreat();                      //頭插法建立連結清單
	head = TailCreat();                      //尾插法建立連結清單
	length = Length(head);
	print(head);
	printf("\n");

	printf("請輸入要插入的數值：");
	scanf("%c",&value);
	printf("%c\n",value);

	printf("請輸入要插入的位置：");
	scanf("%d",&x);
	printf("%d\n",x);

	Insert(head, x, value, length);            //向連結清單中特定位置插入一個元素
	print(head);
	printf("\n");

	printf("請輸入要删除的結點：");
	scanf("%d",&x);
	Delete(head, x, length);                   //删除一個結點
	print(head);

	return 0;
}

list HeadCreat()                                //頭插法建立連結清單
{
	list head;
	char c;
	int flag = 1;

	head = (list)malloc(sizeof(node));          //頭結點，裡面沒有資料
	if(!head)
		printf("連結清單建立錯誤！");
	head->next = NULL;

	while(flag == 1)
	{
		printf("請輸入資料：");
		c = getchar();
		flushall();                             //清除enter所産生的緩存資料

		if(c != '$')
		{
			node *w;
			w = (node *)malloc(sizeof(node));

			w->data = c;
			w->next = head->next;
			head->next = w;
		}
		else
			flag = 0;		
	}
	return head;
}

list TailCreat()                                 //尾插法建立連結清單
{
	list head;
	node *p;
	char c;
	int flag = 1;

	head = (list)malloc(sizeof(node));           //頭結點，裡面沒有資料
	if(!head)
		printf("連結清單建立錯誤！");
	p = head;
	p->next = NULL;
	head->next = NULL;
	while(flag == 1)
	{
		printf("請輸入資料：");
		c = getchar();
		flushall();                              //清除enter所産生的緩存資料

		if(c != '$')
		{
			node *w;
			w = (node *)malloc(sizeof(node));
			w->data = c;
			p->next = w;
			p = w;
		}
		else
			flag = 0;
			p->next = NULL;
		
	}
	return head;
}

int Length(list head)                              //統計連結清單的長度 
{
	node *p;
	int i = 0;

	p = head->next;

	while(p)
	{
		p = p->next;
		i++;
	}

	return i;
}


void Insert(list head, int x, char value, int length)//向連結清單中特定位置插入一個元素
{
	node *pre, *p;                                //*pre為要插入位置的前驅結點
	int i = 1;

	pre = head;
	p = (node *)malloc(sizeof(node));

	while(i < x)
	{
		pre = pre->next;
		i++;
	}

	if(i > length)
	{
		printf("插入錯誤！\n");
	}
	else
	{
		p->data = value;
		p->next = pre->next;
		pre->next = p;
	}
}

void Delete(list head, int x, int length)        //删除一個結點
{
	node *pre, *p;                              //*per為要删除結點的前驅結點，*hid為要删除的結點
	int i = 1;

	p = head;

	if(x > length)
		printf("輸入結點位置錯誤！\n");
	else
	{
		while(i <= x)
		{
			pre = p;
			p = p->next;
			i++;
		}
		pre->next = p->next;
	}
}

void print(list head)                             //輸對外連結表

{
	node *p;
	p = head->next;
	for(; p != NULL; p = p->next)
		printf("%c ",p->data);
}