分类：数据结构

字符串全排列

/**
 * Created by zzh on 2018/12/30.
 */
public class Test {
    public static List<List<Character>> allSort(List<Character> chars){
        if(chars.size() == 1) {
            List<List<Character>> list = new ArrayList<>();
            list.add(chars);
            return list;
        }

        List<List<Character>> list = new ArrayList<>();

        List<Character> useList = new ArrayList<>();
        List<Character> others = new ArrayList<>(chars);

        for (Character ch : chars) {

            if (useList.contains(ch)) {
                // 如果已经使用过重复元素的一个,就不再使用
                continue;
            } else {
                // 记录使用过的元素
                useList.add(ch);
            }

            // 移除当前的元素,得到剩下的元素
            others.remove(ch);

            // 拿剩下的数据进行全排列
            List<List<Character>> othersAllSort = allSort(others);

            // 当前的元素和剩下的元素的全排列,拼接下就可以了
            for (List<Character> othersAllSortItem : othersAllSort) {
                List<Character> dest = new ArrayList<>(othersAllSortItem);
                dest.add(0, ch);

                list.add(dest);
            }

            // 恢复元素列表,便于下次循环复用
            others.add(ch);
        }

        return list;
    }

    public static void main(String[] args){
        List<Character> src = Arrays.asList('a', 'a', 'b');
        
        List<List<Character>> allSortList = allSort(src);

        allSortList.forEach(Test::print);
    }

    private static void print(List<Character> chars){
        for (Character ch : chars) {
            System.out.print(ch + " ");
        }
        System.out.println();
    }
}

a a b
a b a
b a a

线性表（LinearList）

InitList(&L)
DestroyList(&L)

ClearList(&L)

ListEmpty(L)
ListLength(L)

GetElem(L, i, &e)
LocateElem(L, e, compare())

PriorElem(L, e, &pre)
NextElem(L, e, &next)

ListInsert(&L, i, e)
ListDelete(L, i, &e)
ListTraverse(L, visit())

线性表

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef struct {
    ElemType *elem;
    int length;
    int listsize;
}SqList;

Status InitList_Sq(SqList &L){
    L.elem = (ElemType*) malloc(LIST_INIT_SIZE * sizeof(ElemType));
    if(!L.elem) exit(OVERFLOW);

    L.length = 0;
    L.listsize = LIST_INIT_SIZE;

    return OK;
}

Status ListInsert_Sq(SqList &L, int i, ElemType e){
    if(i < 1 || i > L.length + 1) return ERROR;

    if(L.length >= L.listsize){
        newbase = (ElemType*) realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));
        if(!newbase) exit(OVERFLOW);

        L.elem = newbase;
        L.listsize += LISTINCREMENT;
    }

    q = &(L.elem[i - 1];
    for(p = &(L.elem[L.length - 1]; p >= q; —p){
        *(p + 1) = *p;
    }
    *q = e;
    ++L.length;

    return OK;
}

Status ListDelete_Sq(SqList &L, int i, ElemType &e){
    if( i < 1 || i > L.length) return ERROR;

    p = &(L.elem[i - 1];
    e = *p;
    q = L.elem + L.length - 1;

    for(++p; p <= q; ++p){
        *(p - 1) = *p;
    }

    —L.length;
    return OK;
}

线性链表

  • 单链表
typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

void CreateList_L(LinkList &L, int n){
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;

    for(i = n; i > 0; --i){
        p = (LinkList)malloc(sizeof(LNode));
        scanf(&p->data);
        p->next = L->next;
        L->next = p;
    }
}