test02.txt

嵌入式C语言培训课件

#include <malloc.h>
#define M 10
typedef int Elemtype;
typedef struct NODE
{
	Elemtype data;
	struct NODE *next;
}SNode;

int a[M] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
//创建一个链表
SNode* CreateTable()
{
	int i = 0;
	SNode *q = NULL;
	SNode *pHead = (SNode*)malloc(sizeof(SNode));
	pHead->data = a[i];
	q = pHead;
	for (i=1; i<M; i++)
	{
		SNode* s = (SNode*)malloc(sizeof(SNode));
		s->data = a[i];
		s->next = NULL;
		q->next = s;
		q = s;
	}
	return pHead;
}

//求长度
int GetLength(SNode* p)
{
	int n = 0;
	SNode *q = p->next;
	while (NULL != q)
	{
		n++;
		q = q->next;
	}
	return (n);
}

//取单链表中第i个节点的位置
SNode* GetNodeByAddr(SNode* pHead, int i)
{
	int j = 0;
	SNode *q = pHead;
	while (j<i && q !=NULL)
	{
		q = q->next;
		j++;
	}
	if (NULL == q)
	{
		printf("位置参数%d不正确\n");
	}
	return (q);
}

//按值查找
int GetNodeByValue(SNode *pHead, Elemtype x)
{
	int i = 0;
	SNode *q = pHead;
	while ( NULL!=q && q->data!=x)
	{
		q = q->next;
		i++;
	}
	if (q == NULL)
	{
		return (-1);
	}
	return (i);
}

//插入节点
void InsNode(SNode *&p, Elemtype x, int i)
{
	SNode *s, *q;
	s = (SNode*)malloc(sizeof(SNode));
	s->data = x;
	if (i==0)
	{
		s->next = p;
		p = s;
	}
	else
	{
		q = GetNodeByAddr(p, i-1);
		if (q==NULL)
		{
			return;
		}
		else
		{
			s->next = q->next;
			q->next = s;
		}
	}
}

//删除节点
void DelNode(SNode *p, int i)
{
	SNode *q, *t;
	if (i == 0)
	{
		t = p->next;
		p->next = t->next;
		free (t);
	}
	else
	{
		q = GetNodeByAddr(p, i-1);
		if (p == NULL)
		{
			return;
		}
		else
		{
			t = q->next;
			q->next = t->next;
			free (t);
		}
	}
}
//显示单链表
void Display(SNode* p)
{
	int i;
	int n = GetLength(p);
	SNode *q = p;
	printf("单链表显示：");
	if (n == 0)
	{
		printf("空表");
	}
	else if (n == 1)
	{
		printf("%d", q->data);
	}
	else
	{
		for (i=0; i<n; i++)
		{
			printf("%d-->", q->data);
			q = q->next;
		}
		printf("%d\n", q->data);
	}
}

int main(int argc, char* argv[])
{
	SNode* pHead = CreateTable();
	Display(pHead);

	InsNode(pHead, 100, 5);
	Display(pHead);

	DelNode(pHead, 5);
	Display(pHead);

	InsNode(pHead, 100, 0);
	Display(pHead);
	return 0;
}