线性表不完整总结

心已赠人 2022-12-24 13:54 139阅读 0赞

线性表

1.  定义: 相同 数据类型的数据元素的 有限 序列
2.  空表
3.  位序
4.  表头元素 表尾元素
5.  前驱后继

线性表的基本操作

1.  InitList(&L): 初始化线性表, 构造空表,分配内存空间
2.  DestroyList(&L): 销毁线性表,释放内存空间
3.  ListInsert(&L, i, e): 插入操作,在第i个位置上插入指定元素
4.  ListDelete(&L, i, &e): 删除第i个位置的元素,并用e返回删除元素的值
5.  LocateElem(&L, e): 按值查找
6.  GetElem(&L, i): 按位查找

其他常用操作  
Lenght(L): 求表长  
PrintList(L): 输出表  
Empty(L): 判表空  
PriorElem(L, cur\_e, &pre\_e)  
NextElem(L, cur\_e, &next\_e)  
ListTraverse(L, visit())  
//注意函数指针作参数的用法。  
//函数名本质就是函数代码区首地址值  
//可作为指针类型的形参进行传递

数据结构的基本操作-创建,销毁,增删,该查

线性表的顺序实现(Sq:sequence 顺序,序列)
    const int LIST_INIT_SIZE = 100;
    const int LISTINCREMENT = 10;
    typedef struct {
        
    	ElemType *elem;
    	int length;
    	int listsize;
    }SqList;
    
    Status InitList_Sq(SqList &L)
    {
        
    	L.elem = (ElemType*)malloc(sizeof(ElemType));
    	if (L.elem == NULL) exit(0);
    	L.length = 0;
    	L.listsize = LIST_INIT_SIZE;
    	return OK;
    }
    
    Status DestroyList_Sq(SqList &l)
    {
        
    	free(L.elem);
    }
    
    Status ListInsert_Sq(SqList &L, int i, ElemType e)
    {
        
    	if (i <= 0 || i >= L.length + 2) return ERROR;
    	//扩容操作
    	if (L.length == L.listsize)
    	{
        
    		L.elem = (ElemType*)realloc(sizeof(ElemType) * (L.listsize + LISTINCREMENT));
    		if (L.elem == NULL) exit 0;
    		L.listsize = (L.listsize + LISTINCREMENT);
    	}
    	ElemType *q = L.elem + i - 1;
    	ElemType *p = L.elem + L.length - 1;
    	while (p >= q)
    	{
        
    		*(p + 1) = *p;
    		p--;
    	}
    	*q = e;
    	L.length++;
    	return OK;
    }
    
    void ListDelete_Sq(SqList &L, int i, ElemType &e)
    {
        
    	if (i <= 0 || i >= L.length + 1) return ERROR;
    	ElemType *p = L.elem + i - 1;
    	ElemType *q = L.elem + L.length - 1;
    	e = *p;
    	while (p < q)
    	{
        
    		*p = *(p + 1);
    		p++:
    	}
    	L.lengh--;
    	return OK;
    }
    
    Status equal(ElemType e1, ElemType e2)
    {
        
    	if (e1 == e2) return TRUE;
    	else return FALSE;
    }
    
    void GetElem_Sq(SqList L, int k, ElemType &e)
    {
        
    	e = L.elem + k - 1;
    }
    int LocateElem_Sq(SqList L, ElemType e, Status(*compare)(ElemType, ElemType))
    {
        
    	ElemType *p = L.elem;
    	int i = 1;
    	while (i <= L.lengh && compare(*p, e) == FALSE)
    	{
        
    		p++;
    		i++;
    	}
    	if (i <= L.lengh) return i;
    	else return 0;
    }
    
    void Union_Sqlist(SqList &La, SqList Lb)
    {
        
    	int la_len = ListLength(La);
    	int lb_len = ListLength(Lb);
    	for (int i = 1; i < lb_len; i++)
    	{
        
    		GetElem(Lb, i, e);
    		if (LocateElem(La, e) == 0)
    		{
        
    			ListInsert(La, la_len + 1, e);
    			la_len++;
    		}
    	}
    }
    
    Status ListMerge_SortedSq(SqList La, SqList Lb, SqList &Lc)
    {
        
    	int la_len = ListLenght(La);
    	int lb_len = ListLenght(Lb);
    	int i = 1, j = 1, k = 1;
    	ElemType a, b;
    	InitList_Sq(Lc);
    	while (i <= la_len && j <= lb_len)
    	{
        
    		GetElem_Sq(La, i, a);
    		GetElem_Sq(Lb, j, b);
    		if (a <= b)
    		{
        
    			ListInsert_Sq(Lc, k, a);
    			i++;
    			k++;
    		}
    		else
    		{
        
    			ListInsert_Sq(Lc, k, b);
    			j++;
    			k++;
    		}
    	}
    	while (i <= la_len)
    	{
        
    		GetElem_Sq(La, i, a);
    		ListInsert_Sq(Lc, k, a);
    		i++;
    		k++;
    	}
    	while (j <= lb_len)
    	{
        
    		GetElem_Sq(Lb, j, b);
    		ListInsert_Sq(Lc, k, b);
    		j++;
    		k++;
    	}
    	return OK;
    }
    线性表的链式实现
    结点包含数据域和指针域
    元素结点前通常添加 头结点
    尾结点指向空
    
    typedef struct LNode
    {
        
    	ElemType data;
    	struct LNode *next;
    }LNode, *LinkList;
    
    Status InitList_L(LinkList &L)
    {
        
    	L = (LNode*)malloc(sizeof(LNode));
    	L->next =  NULL;
    	return OK;
    }
    Status DestroyList_L(LinkList &L)
    {
        
    	//伴随指针
    	LNode *p, *q;
    	p = L;
    	q = L->next;
    	while (q != NULL)
    	{
        
    		free(p);
    		p = q;
    		q = q->next;
    	}
    	//之前while的边界我写成了p != NULL
    	//但是这样会发生 访问空指针 的error
    	free(p);
    }
    Status ListInsert_L(LinkList &L, int i, ElemType e)
    {
        
    	//可能从空链表开始插入元素
    	//所以 不能让p = L->next
    	//否则可能会出现访问空指针的错误
    	LNode *p = L;
    	int j = 0;
    	//还是让首元素结点下标为1 
    	//因此头结点的下标 是0, 即使头结点的下标没有意义
    	//但是便于 写代码
    	while (p && j < (i - 1) - 1)
    	{
        
    		p = p->next;
    		j++;
    	}
    	//结束循环后,p指向的是 下标为i-1的位置
    	//若[i-1]也是NULL,不能插入元素
    	//错误输入
    	if (p == NULL ||i <= 0) return ERROR;
    	
    	LNode temp_node = (LNode*)malloc(sizeof(LNode));
    	if (temp_node == NULL) return ERROR;
    	q->data = e;
    	q->next = p->next;
    	p->next = temp_node;
    	return OK;
    }
    
    Status ListDelete_L(LinkList &L, int i, ElemType &e)
    {
        
    	LNode *p, *q;
    	p = L;
    	int j = 0;
    	while (p && j <= (i - 1) - 1)
    	{
        
    		p = p->next;
    		j++;
    	}
    	//可能[i-1]就是NULL 也可能[i]是NULL 也可能位置不合法
    	if (p == NULL || p->next == NULL || i <= 0) return ERROR;
    	
    	q = p->next;
    	e = q->data;
    	p->next = q->next;
    	free(q);
    	return q;
    }
    
    Status GetElem_L(LinkList L, int i, ElemType &e)
    {
        
    	LNode *p = L;
    	int j = 1;
    	while (p && j <= i)
    	{
        
    		p = p->next;
    		j++;
    	}
    	if (p == NULL || i <= 0) return ERROR;
    	e = p->data;
    	return OK;
    }
    
    //链表的其他操作
    //逆位序创建n个结点的链表
    Status ListCreate_L(SqList &L, int n)
    {
        
    	LNode *p;
    	L = (LNode*)malloc(sizeof(LNode) * 1);
    	if (L == NULL) exit OVERFLOW;
    	L->next = NULL;
    	for (int i = 0; i < n; i++)
    	{
        
    		p = (LNode*)malloc(sizeof(LNode) * 1);
    		cin >> p->data;
    		p->next = L->next;
    		L->next = p;
    	}
    }
    
    //归并(融合)非降序链表
    void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc)
    {
        
    	LNode *pa = La->next;
    	LNode *pb = Lb->next;
    	//notice this codeline
    	LNode *pc = Lc = La;
    	
    	while (pa && pb)
    	{
        
    		if (pa->data <= pb->data)
    		{
        
    			pc->next = pa->next;
    			pa = pa->next;
    			pc = pc->next;
    		}
    		else 
    		{
        
    			pc->next = pb->next;
    			pb = pa->next;
    			pc = pc->next;
    		}
    	}
    	//notic this codeline(nttcdl)
    	if (pa) pc->next = pa;
    	if (pb) pc->next = pb;
    	free(Lb);
    }
    
    typedef struct DuLNode
    {
        
    	ElemType data;
    	
    	struct DuLNode *prior;
    	struct DuLNode *next;
    }DuLNode, *DuLinkList;
    
    Status ListInsert_DuL(DuLinkList &L, int i, ElemType e)
    {
        
    	DuLNode *p = L;
    	int j = 0;
    	while (p && j <= (i-1) - 1)
    	{
        
    		p = p->next;
    		j++;
    	}
    	DuLNode *temp_Node = new DuLNode;
    	if (temp_Node == NULL) exit(OVERFLOW);
    	temp_Node->prior = p;
    	temp_Node->next = p->next;
    	p->next = s;
    	s->next->prior = s;
    	return OK;
    }
    Status ListDelete_DuL(DuLinkList &L, int i, ElemType &e)
    {
        
    	if (!(p = GetElem_DuL(L, i))) return ERROR;
    	e = p->data;
    	p->prior->next = p->next;
    	p->next->prior = p->prior;
    	free(p);
    	return OK;
    }
    
    线性表的应用--稀疏多项式
    顺序表实现
    typedef struct 
    {
        
    	float coef;
    	int expn;
    }Term;
    typedef Term ElemType;
    typedef LinkList Polynomial;
    
    Polynomial CreatePolyn(Polynomial &P, int m)
    {
        
    	return ListCreate_L(P, m);
    }
    
    void Insert(Polynomial &P, Polynomial q)
    {
        
    	LNode *prep, *p;
    	prep = P;
    	p = prep->next;
    	//p的结果是 第一个 NULL 或者 第一个 大于等于p的
    	while (p && p->data.expn < q->data.expn)
    	{
        
    		prep = p;
    		p = p->next;
    	}
    	if (p == NULL)
    	{
        
    		prep->next = q;
    		q->next = NULL;
    	}
    	else 
    	{
        
    		if (p->data.expn == q->data.expn)
    		{
        
    			if (p->data.coef + q->data.coef)
    			{
        
    				prep->next = p->next;
    				free(p);
    			}
    			else 
    			{
        
    				p->data.coef += q->data.coef;
    			}
    		}
    		else 
    		{
        
    			prep->next = q;
    			q->next = p;
    		}
    	}
    }
    Status CreatePolyn(Polynomial &P, int n)
    {
        
    	LNode *rearPtr, *q;
    	if (n < 0) return ERROR;
    	P = (LNode*)malloc(sizeof(LNode) * 1);
    	if (P == NULL) exit(OVERFLOW);
    	P->next = NULL;
    	for (int i = 1; i <= n; i++)
    	{
        
    		q = (LNode*)malloc(sizeof(LNode));
    		if (q == NULL) exit(OVERFLOW);
    		Input(q->data);
    		Insert(P, q);
    	}
    	return OK;
    }
    
    Status PrintPolynomial(Polynomial P)
    {
        
    	return ListPirnt_L(P);
    }