HZNUOJ

【数据结构】链表

Tags:
Time Limit:  1 s      Memory Limit:   128 MB
Submission:188     AC:26     Score:98.53

Description

链表的插入流程如下图所示:
第一步:
新插入节点s的next指针指向p节点的next指针

第二步:

将p->next 指向s



完成以上两步之后,即完成了新节点的插入。
节点的删除过程与上图类似。
现在阅读以下程序,并补全


Status ListInsert(NHead *head, int pos, ElemType e);
Status ListDelete(NHead *head, int pos);


两个函数,使得程序能够完成新节点的插入或删除某个位置的元素

元素下标从0开始


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int ElemType;
typedef int Status;
typedef struct Node
{
	ElemType data;
	struct Node *next;
}Node;
typedef Node *NPointer;
typedef struct NHead
{
	int length;
	NPointer next;
}NHead;
Status InitList(NHead *head)
{
	head->length = 0;
	head->next = NULL;
	return OK;
}
Status ClearList(NHead *head)
{
	head->length = 0;
	while (head->next)
	{
		NPointer tmp = head->next;
		head->next = head->next->next;
		free(tmp);
	}
	return OK;
}
Status ListIsEmpty(NHead *head)
{
	if (head->length)return FALSE;
	else return TRUE;
}
int ListLength(NHead *head)
{
	return head->length;
}
Status GetElem(NHead *head, int pos, ElemType *e)
{
	NPointer now = head->next;
	int cot = 0;
	while (now&&cot < pos)
	{
		now = now->next;
		cot++;
	}
	if (!now || cot >= pos)return ERROR;
	*e = now->data;
	return OK;
}
int LocateElem(NHead* head, ElemType e)
{
	int cot = 0;
	NPointer now = head->next;
	while (now)
	{
		if (now->data == e) /* 找到这样的数据元素 */
			break;
		now = now->next;
		cot++;
	}
	return cot;
}
void ListVisit(ElemType e)
{
	printf("%d", e);
}
Status ListTraverse(NHead *head)
{
	NPointer now = head->next;
	int cot = 0;
	while (now)
	{
		if (cot)printf(" ");
		ListVisit(now->data);
		cot++;
		now = now->next;
	}
	printf("\n");
	return OK;
}
Status ListInsert(NHead *head, int pos, ElemType e);
Status ListDelete(NHead *head, int pos);
int main()
{
	NHead head;
	InitList(&head);
	int n;
	scanf("%d", &n);
	char ctl[10];
	for (int i = 0; i < n; i++)
	{
		scanf("%s", ctl);
		if (strcmp(ctl, "add") == 0)
		{
			int x, y;
			scanf("%d%d", &x, &y);
			ListInsert(&head, x, y);
		}
		else if (strcmp(ctl, "find") == 0)
		{
			int x;
			scanf("%d", &x);
			int pos = LocateElem(&head, x);
			if (pos == ListLength(&head))puts("No such element");
			else printf("%d\n", pos);
		}
		else if (strcmp(ctl, "delete") == 0)
		{
			int x;
			scanf("%d", &x);
			if (ListDelete(&head, x))puts("OK");
			else puts("ERROR");
		}
		else if (strcmp(ctl, "traverse") == 0)
		{
			ListTraverse(&head);
		}
		else if (strcmp(ctl, "clear") == 0)
		{
			
			ClearList(&head);
		}
	}
	return 0;
}


你只需要提交两个函数即可