practice - decoqt/mywiki GitHub Wiki

#practice

##目录 1.基础操作
    1.1 顺序表
    1.2 链表
    1.3 栈
    1.4 队列
2.题目

基础操作

###1. 顺序表

#define InitSize 100;
typedef struct {
	Elemtype *data;
	int Maxsize,length;
}Sqlist;

####初始化

	Linklist init(Sqlist &L)
	{
		L.data = (Elemtype *)malloc(sizeof(Elemtype)*InitSize);
		if(!L.data)
			return -1;
		L.length = 0;
		L.listsize = InitSize;
		return 0;
	}

###2. 单链表

typedef struct LNode{
	Elemtype data;
	struct LNode *next;
}LNode,*Linklist;

####初始化

  • 头插法

      Linklist init(Sqlist &L)
  {
  	LNode *s;int x;
  	L = Linklist malloc(sizeof(LNode));
  	if(!L)
  		return -1;
  	L->next = NULL;
  	scanf("%d",x);
  	while (x != ) {
  		s =  (LNode *)malloc(sizeof(LNode));
  		s->data = x;
  		s->next = L->next;
  		scanf("%d",x);
  	}
  
  	return L;
  }

  • 尾插法

      Linklist init(Sqlist &L)
  {
  	int x;
  	L = Linklist malloc(sizeof(LNode));
  	if(!L)
  		return -1;
  	LNode *s,*r = L;
  	scanf("%d",x);
  	while (x != ) {
  		s =  (LNode *)malloc(sizeof(LNode));
  		s->data = x;
  		r->next = s;
  		r = s;
  		scanf("%d",x);
  	}
  	r->next = NULL;
  	return L;
  }

####寻找结点

####插入结点

####删除结点

###3. 栈

####初始化

  • 顺序栈

      #define Maxsize 50
  typedef struct{
  	Elemtype data[Maxsize];
  	int top;
  }Sqstack;

  void Init_stack(&s){
  	s.top = -1;
  }

  • 链栈

      typedef struct Linknode{
  	Elemtype data;
  	struct Linknode *next;	
  }*Listack;

    类似单链表实现

####判空 bool stack_empty(SqStack s){ if(s.top == -1) return true; else return false; }

####进栈

	bool push(SqStack &s,Elemtype e)
	{
		if (s.top == Maxsize-1)
			return false;
		s.data[++s.top] = e;
		return true;
	}

####出栈

	bool pop(Sqstack s,Elemtype e)
	{
		if(s.top == -1)
			return false
		e = s.data[s.top--];
		return true;
	}

###4. 队列

####初始化

  • 顺序队列

      #define Maxsize 50
  typedef struct{
  	Elemtype data[Maxsize];
  	int front,rear;
  }SqQueue;

  • 链式队列

      typedef struct{
  	Elemtype data;
  	struct Linknode *next;	
  }Linknode;
  
  typedef struct {
  	Linknode *front,*rear;
  }LinkQueue;
  
  void InitQueue(LinkQueue &Q){
  	Q.front = Q.rear = (Linknode *)malloc(sizeof(Linknode));
  	Q.front->next=NULL;
  }

####判断空

bool queue_empty(SqQueue Q){
	if(Q.front == Q.rear)
		return true;
	else
		return false;
}

####入队

bool Enqueue(SqQueue &Q,Elemtype e){
	Linknode *s = (Linknode *)malloc(sizeof(Linknode));
	s->data = e;
	s->next = NULL;
	Q.rear->next = s;
	Q.rear = s; 
}

####出队

bool Dequeue(SqQueue &Q.Elemtye &e){
	if(queue_empty(Q))
		return false;
	Linknode *p = Q.front->next;
	e = p->data;
	Q->next = p->next;
	if (Q.rear = p)
		Q.rear = Q.front;
	free ( p );
	return true;
}

删除所有值为x的数据元素

###顺序表

void del_x(Sqlist &L,Elemtype x) {
	int i = 0,k = 0;
	for (i = 0; i < L.length; i++){
		if(L.data[i] == x){
			L.data[k] = L.data[i+1];
			k++;
		}
	}
	L.length = k;
}

###单链表 void del_x(Sqlist &L,Elemtype x) { LNode *p = L->next,*q; while ( p ) { if ( p->data == x ){ q=p->next; p->data = q->data; p->next = q->next; free(q) } else p=p->next; } }

##2. 单链表排序

Linklist list_sort(Sqlist &L){
	Lnode *p = L->next,*q = L->next;
	while ( p ){
		while ( q )
			if (q->data < p->data){
				swap(q->data,p-data);
				q = q->next;
			}
		p=p->next;
	}
}

##3. 逆置单链表

Linklist reverse (Sqlist &L){
	Lnode *p = L->next,*r;
	L->next = Null;
	while ( p ) {
		r = p->next;
		p->next = L->next;
		L->next = p;
		p = r;
	}
	return L;
}

##4. 合并有序链表

Linklist merge(Sqlist &L,Sqlist &S) {
	Lnode *pa = L->next,*pb = S->next,r;
	L->next = NULL;
	while( pa && pb ) {
		if(pa->data < pb->data){
			r = pa->next;
			pa->next = L->next;
			L->next = pa;
			pa=r;
		}
		else {
			r = pb->next;
			pb->next = L->next;
			L->next = pb;
			pb=r;
		}
	}
	if(pa)
		pb = pa;
	while (pb){
		r = pb->next;
		pb->next = L->next;
		L->next = pb;
		pb=r;
	}	
	free(S);
	reverse(L);		
}

找出最大的元素

Lnode find_max(Sqlist L){
	Lnode *p = L->next,*q;
	q=p;
	while ( p ){
		if(p->data > q->data)
			q = p;
		p = p->next;
	}
	return q;
}
⚠️ **GitHub.com Fallback** ⚠️